Haskell Infinite Type

Question

J'essaye d'obtenir le code ci-dessous fonctionnant. C'est une machine à états finis où je passe dans une fonction-comme-état-suivant. La fonction est appelée avec r et renvoie une liste de résultats + le prochain état de fonction-comme-suivant. Continuez à appeler jusqu'à épuisement de la liste et renvoyez la concaténation des résultats. La monade est une monade d'erreur pour me permettre de lancer une erreur si nécessaire.

fsm f []  = return [] 
fsm f (r:rs) = do 
    (xs, f') <- f r 
    rest  <- fsm f' rs 
    return $ xs ++ rest 

L'erreur est:

Occurs check: cannot construct the infinite type: t1 = t0 -> m0 ([a0], t1) 
In the first argument of `fsm', namely f' 

Je l'ai vu l'erreur de type infini avant et je comprends la manière autour d'elle est d'envelopper un type avec un newtype. Mais je ne peux pas comprendre comment faire cela.

Quelqu'un peut-il souligner le point de vue?

Answer 1

Je pense que c'est ce que vous voulez:

newtype F m = F { unF :: String -> m ([String], F m) } 

fsm :: (Monad m) => F m -> [String] -> m [String] 
fsm f []  = return [] 
fsm f (r:rs) = do 
    (xs, f') <- unF f r 
    rest  <- fsm f' rs 
    return $ xs ++ rest 

Vous avez raison que vous devez utiliser un data ou newtype chaque fois que vous voulez un type récursif.

En réponse à votre commentaire, voici comment vous mettre en œuvre votre fonction dup:

dup :: (Monad m) => F m 
dup = F dup' where dup' xs = return ([xs, xs], F dup') 

... ou vous pouvez le diviser en deux définitions distinctes si vous préférez.

Notez que si vous n'êtes pas sûr de ce que la signature de type doit être, il suffit d'activer l'extension NoMonomorphismRestriction et le compilateur ne se plaindra pas et déduira correctement le type de niveau supérieur pour vous.