cps dans "encore un autre haskell turorial"

Question

J'apprends le haskell en lisant le livre "Yet Another Haskell Tutorial", et je rencontre un problème quand vient le style passant de la contiuation. Le livre donne un cps se replient comme:

cfold’ f z [] = z 
cfold’ f z (x:xs) = f x z (\y -> cfold’ f y xs) 

et donne le résultat du test:

CPS> cfold (+) 0 [1,2,3,4] 
10 
CPS> cfold (:) [] [1,2,3] 
[1,2,3] 

mais, lorsque je tente de le tester, je trouve qu'il ya un problème, le ghci donne:

*Main> cfold (+) 0 [] 

<interactive>:8:7: 
    Occurs check: cannot construct the infinite type: 
     t10 = (t10 -> t10) -> t10 
    Expected type: t10 -> t10 -> (t10 -> t10) -> t10 
     Actual type: t10 -> t10 -> t10 
    In the first argument of `cfold', namely `(+)' 
    In the expression: cfold (+) 0 [] 
    In an equation for `it': it = cfold (+) 0 [] 

Il est logique pour moi, donc je changer la définition de cps à quelque chose comme ceci:

cfold f z [] = z 
cfold f z (x:xs) = (\y -> cfold f y xs) (f x z) 

Et cela fonctionne très bien:

*Main> cfold (+) 0 [1,2,3] 
6 

Ma question vient, est-il un bug dans le livre ou quelque chose qui me manque ici?

Answer 1

Je ne pense pas qu'il y ait une erreur dans le livre. La fonction cfold' dans le livre prend une fonction dans le style passant contiuation, donc la fonction que vous passez à cfold' doit prendre 3 arguments: l'accumulateur, l'élément de liste en cours et la poursuite, à laquelle passer le résultat.

(+) prend seulement deux arguments, car il n'est pas dans le style cps, donc vous ne pouvez pas utiliser la fonction cfold '. Pour résumer les éléments d'une liste à l'aide cfold », vous pouvez écrire:

> cfold' (\e acc cont -> cont (acc + e)) 0 [3,2,4] 
9 

Notez que le lambda prend trois arguments: l'élément, l'accumulateur et la poursuite. La suite est une fonction qui dit "que faire ensuite", compte tenu du résultat du calcul actuel. Donc, en appelant la continuation à chaque fois, vous traitez l'élément suivant.

Alors, que pensez-vous qu'il se passe quand je n'appelle pas la suite? Puis-je peut-être arrêter de traiter la liste de cette façon, pour implémenter quelque chose comme takeWhile? Dans cet exemple, nous n'appelons pas la continuation lorsque l'élément est supérieur à 3, donc nous arrêtons le traitement de la liste. Sinon, nous ajoutons l'élément à l'accumulateur, c'est pourquoi la liste est inversée. Comme le montre l'exemple, cela fonctionne bien avec des listes infinies.

Et, vous pouvez aussi écrire une fonction qui transforme toute fonction 2 argument qui n'est pas cps style à cps style:

toCps2 :: (a -> b -> c) -> (a -> b -> (c -> d) -> d) 
toCps2 f = \a b c -> c (f a b) 

Cette fonction passe juste le résultat de l'application de la non-cps fonction à la continuation. Vous pouvez utiliser cette fonction pour mettre en œuvre votre cfold, qui prend une fonction qui ne sont pas dans le style cps à plier une liste:

cfold :: (a -> b -> c) -> b -> [a] -> c 
cfold f = cfold' (toCps2 f) 

Avec cette fonction, vous pouvez maintenant utiliser (+) à plier votre liste:

> cfold (+) 0 [3,2,4] 
9 

Answer 2

Dans le Encore un autre Haskell Tutorial est également une définition de cfold

cfold f z l = cfold' (\x t g -> f x (g t)) z l 

Cette fonction cfold utilise cfold »

Dans le WinHugs-environnement, il travaille D'ACCORD.