Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #59 da revista programar. Faz já o download aqui!

miguelsilva94

Melhorar implementação geradores quickcheck

Mensagens Recomendadas

miguelsilva94    0
miguelsilva94

Boa tarde,

Tenho uma dúvida em relação a propriedade quickcheck. Não sei se me podem ajudar, de qualquer forma deixo a dúvida. Obrigado desde já.

Grafos têm estas propriedades:

O tipo Edge representa uma aresta entre dois nodos

data Edge v = Edge {source :: v, target :: v}
	  deriving (Show,Eq,Ord)

O tipo Graph representa um grafo orientado

data Graph v = Graph {nodes :: Set v, edges :: Set (Edge v)}
              deriving Show

A função isDAG testa se um grafo é acíclico.

isDAG :: Ord v => Graph v -> Bool
isDAG g = isValid g && all nocycle (nodes g)
where nocycle v = all (\a -> v `notMember` reachable g a) $ Set.map target (adj g v)

A função isForest testa se um grafo acíclico é uma floresta, ou seja, um conjunto de árvores

isForest :: Ord v => DAG v -> Bool
isForest g = isDAG g && all (\v -> length (adj g v) <= 1) (nodes g)

Os geradores

Gerador de DAGs

dag ::(Ord v, Arbitrary v)=> Gen (DAG v)
dag = arbitrary `suchThat` isDAG

Gerador de Florestas

forest ::(Ord v, Arbitrary v)=> Gen (Forest v)
forest = arbitrary `suchThat` isForest

Estes geradores são necessários para testar propriedades sobre estas classes de grafos.

Usando os combinadores para definir propriedades quickcheck, como melhoro a implementação destes geradores por forma a serem menos enviesados (sem estarem definidos com o suchThat)?

Editado por miguelsilva94
Removida formatação desnecessária. Syntax highlight.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
SoberDrunk    1
SoberDrunk

Olá,

Não tenho nenhuma sugestão concreta para o teu problema - concordo que usando o suchThat não é a forma mais eficiente.

Noto apenas que na definição do tipo Graph repetiste a definição de Edge.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.