Início / coding / Perguntas / 79553310
Accepted
Simon Abadi
Asked: 2025-04-03 23:03:24 +0800 CST

Corrigindo a função andAlso de um gerador Haskell: resultados de teste inconsistentes

  • 772

Estou trabalhando com uma implementação Haskell de geradores para uma tarefa de casa. Tenho uma andAlsofunção que supostamente adiciona um predicado adicional a um gerador, mas não está funcionando corretamente em todos os casos de teste. Embora pareça correto

Aqui está minha definição de tipo de gerador:

-- Type definition for a generator: a function producing a sequence of values
-- 1. The first function generates the next value.
-- 2. The second function checks if generation should continue.
-- 3. The third value is the initial value, or seed. It does not count as being generated by the generator.
type Generator a = (a -> a, a -> Bool, a)

Minha implementação atual de andAlso:

-- Adds an additional predicate to a generator.
andAlso :: (a -> Bool) -> Generator a -> Generator a
andAlso p (f, g, s) = (f, \x -> g x && p x, s)

Estou usando uma função auxiliar takeGenpara visualizar os resultados dos testes:

takeGen :: Int -> ((a -> a), (a -> Bool), a) -> [a]
takeGen 0 _ = []
takeGen n (next, pred, seed)
  | not (pred seed) = []
  | otherwise = seed : takeGen (n-1) (next, pred, next seed)

Casos de teste e resultados

Aqui estão meus casos de teste e seus resultados:

-- Test 1: Filter for odd numbers
takeGen 10 (andAlso (\x -> x `mod` 2 == 1) ((+1), (<10), 0))
-- Expected: [1,3,5,7,9], but getting: [1]

-- Test 2: Filter for numbers divisible by 3
takeGen 10 (andAlso (\x -> x `mod` 3 == 0) ((+1), (<10), 0))
-- Expected: [0,3,6,9], but getting: [0]

-- Test 3: Filter for numbers greater than 5
takeGen 10 (andAlso (>5) ((+1), (<10), 0))
-- Works correctly: [6,7,8,9]

-- Test 4: Combine two additional predicates
takeGen 10 (andAlso (>3) (andAlso (<8) ((+1), (<10), 0)))
-- Works correctly: [4,5,6,7]

-- Test 5: Test with a different generator function
takeGen 10 (andAlso (<15) ((+2), (<20), 1))
-- Works correctly: [1,3,5,7,9,11,13]

takeGen 10 (andAlso (<10) ((+1), (<10), 0))
-- Works correctly: [0,1,2,3,4,5,6,7,8,9]

O que eu tentei

Eu tentei várias implementações de andAlso, incluindo:

  1. A implementação atual mostrada acima
  2. Ajustando como os predicados são aplicados na sequência
  3. Tentando encontrar o primeiro valor válido que satisfaça ambos os predicados

Alguns casos de teste funcionam corretamente, mas outros (especificamente os testes 1 e 2) não retornam todos os valores esperados.

Minha pergunta

O que há de errado com minha andAlsoimplementação e como devo consertar para fazer todos os casos de teste funcionarem conforme o esperado? O problema é com a forma como o gerador é definido, como takeGenfunciona ou como andAlsoaplica o predicado adicional?

Contexto adicional

Outras funções relacionadas ao gerador que implementei:

nthGen :: Integer -> Generator a -> a
nextGen :: Generator a -> Generator a
lengthGen :: Generator a -> Integer
hasLengthOfAtLeast :: Integer -> Generator a -> Bool
constGen :: a -> Generator a
foreverGen :: (a -> a) -> a -> Generator a
emptyGen :: Generator a

Obrigado por qualquer ajuda para entender onde minha implementação está dando errado.

haskell

1 respostas

  1. Best Answer

    Observe que não posso comparar os resultados do seu teste com a versão fornecida do andAlso. (Por exemplo, recebo mais respostas erradas do que você.)

    No entanto, parece que você implementou andAlsoa adição do predicado fornecido à regra de continuação para o gerador, mas os casos de teste indicam que ele deve ser tratado como um filtro para o gerador.

    Por exemplo, para "Teste 1", sua andAlsoimplementação só continua a gerar valores enquanto o predicado (<10)for true AND o predicado \x -> x `mod` 2for true. Mas, para a primeira semente do 0segundo predicado falhar, então esse teste gera uma lista vazia [](que é o que eu obtenho com seu código). Em vez disso, você quer continuar gerando valores enquanto (<10)for bem-sucedido, mas apenas "passar adiante" o subconjunto de valores que satisfazem \x -> x `mod` 2.

    É um pouco complicado implementar andAlsodiretamente, então você pode seguir o conselho de @user2407038 e tentar implementar fromListe toList.

    Mas, se você quer uma solução direta, aqui vão algumas dicas. Considere a definição do template:

    andAlso p (f, g, s) = (f', g', s')

    Vamos fingir que esse gerador nunca para (então ge g'não importa). Como f'e s'deve ser? Bem, você quer s'ser o primeiro valor da Generatorsequência [s, f s, f (f s), ...]que satisfaz p. Então escreva:

    where s' = find p (f, g, s)

    e implementar:

    find :: (a -> Bool) -> Generator a -> a
find p (f, g, a) = ...

    Aqui, finddeve passar por testes como:

    λ> find even ((+1), (<100), 0)
0
λ> find odd ((+1), (<100), 0)
1
λ> find (>10) ((+3), (<100), 0)
12

    Não se preocupe com a regra de parada gainda find... vamos descobrir isso em um momento.

    Agora, o que dizer de f'? Bem, f'precisa avançar rapidamente a semente atual t(seja ela qual for) para a próxima semente na sequência [f t, f (f t), ...]que satisfaça p. Então, será apenas:

    where f' t = find p (f, g, f t)

    (Observe o uso de f tno lugar de tpara garantir que não paramos em t.)

    Agora, que tal parar? Bem, queremos ter cuidado aqui para parar no primeiro valor gerado que falha o predicado g, independentemente de satisfazer ou não nosso filtro predicado p.

    Podemos garantir que isso aconteça modificando findpara que ele pare quando gfor satisfeito, mesmo se a semente resultante falhar p. Isso garantirá que s'seja definido como o valor de parada, então o processamento posterior do gerador será interrompido porque g s'será falso.

    Então, modifique findconforme necessário para que ele passe nos testes acima e também funcione com:

    λ> find (>10) ((+1), (<5), 0)
5

    Ou seja, ele deve "encontrar" o primeiro elemento que falha no predicado de continuação (<5), mesmo que esse elemento não satisfaça o predicado de filtro (>10).

    Com essa versão findem vigor, você deve ser capaz de escrever:

    andAlso :: (a -> Bool) -> Generator a -> Generator a
andAlso p (f, g, s) = (f', g, s')
  where s' = find p (f, g, s)
        f' t = find p (f, g, f t)

    e faça com que ele passe em todos os seus testes.

    • 0

relate perguntas