Récursivité réciproque - quelqu'un peut-il aider à expliquer comment ce code fonctionne?

Question

Je lis dans « A Gentle Introduction à Haskell, » et dès le début il utilise cet exemple, qui fonctionne très bien dans GHC et horriblement dans mon cerveau:

initial     = 0 
next resp    = resp 
process req    = req+1 

reqs     = client initial resps 
resps     = server reqs 

server   (req:reqs) = process req : server reqs 
client initial ~(resp:resps) = initial : client (next resp) resps 

Et le code d'appel:
take 10 reqs

Comment je le vois, est reqs est appelé, produisant un appel à client avec les arguments 0 et resps. Donc, ne devrait pas être appelé resps ... qui à son tour appelle reqs à nouveau? Tout semble si infini ... si quelqu'un pouvait détailler comment cela fonctionne réellement, je serais très reconnaissant!

Answer 1

Je trouve qu'il est généralement intéressant de déterminer le comportement des petits programmes Haskell à la main, les règles d'évaluation sont assez simples. se rappeler est que Haskell est non-strict (aka paresseux): les expressions sont évaluées seulement si nécessaire La paresse est la raison pour laquelle les définitions apparemment infinies peuvent donner des résultats utiles. 10 éléments de la liste infinie reqs: ils sont tout ce dont nous avons besoin

En termes pratiques, le «besoin» est généralement conduit par des correspondances de modèle. Par exemple, une expression de liste sera généralement évaluée jusqu'au point où nous pouvons distinguer entre [] et (x:xs) avant l'application de la fonction. (Notez qu'une « ~ » précédant un motif, comme dans la définition de client, rend paresseux (ou irréfutable.): Un motif paresseux ne forcera son argument jusqu'à ce que toute expression est forcée)

souvenir que take est:

take 0 _  = [] 
take n (x:xs) = x : take (n-1) xs 

l'évaluation des take 10 reqs ressemble à:

take 10 reqs 
     -- definition of reqs 
    = take 10 (client initial resps) 
     -- definition of client [Note: the pattern match is lazy] 
    = take 10 (initial : (\ resp:resps' -> client (next resp) resps') 
          resps) 
     -- definition of take 
    = initial : take 9 ((\ resp:resps' -> client (next resp) resps') 
          resps) 
     -- definition of initial 
    = 0 : take 9 ((\ resp:resps' -> client (next resp) resps') 
         resps) 
     -- definition of resps 
    = 0 : take 9 ((\ resp:resps' -> client (next resp) resps') 
         (server reqs)) 
     -- definition of reqs 
    = 0 : take 9 ((\ resp:resps' -> client (next resp) resps') 
         (server (client initial resps))) 
     -- definition of client 
    = 0 : take 9 ((\ resp:resps' -> client (next resp) resps') 
         (server (initial : {- elided... -})) 
     -- definition of server 
    = 0 : take 9 ((\ resp:resps' -> client (next resp) resps') 
         (process initial : server {-...-})) 
     -- beta reduction 
    = 0 : take 9 (client (next (process initial)) (server {-...-}) 
     -- definition of client 
    = 0 : take 9 (next (process initial) : {-...-}) 
     -- definition of take 
    = 0 : next (process initial) : take 8 {-...-} 
     -- definition of next 
    = 0 : process initial : take 8 {-...-} 
     -- definition of process 
    = 0 : initial+1 : take 8 {-...-} 
     -- definition of initial 
    = 0 : 1 : take 8 {-...-} 
     -- and so on... 

Answer 2

Cela fait longtemps que je n'ai pas joué avec Haskell, mais je suis à peu près sûr qu'il est évalué paresseusement, ce qui signifie qu'il ne calcule que ce dont il a vraiment besoin. Donc, alors que reqs est infiniment récursif, puisque take 10 reqs n'a besoin que des 10 premiers éléments de la liste retournée, c'est tout ce qui est réellement calculé.

Answer 3

Comprendre ce code requiert deux compétences:

• distinction entre « définition », ce qui peut être infinie (comme l'ensemble des nombres naturels: naturals = (1 : map '\n->n+1' naturals), ou la liste des demandes traitées) et « réduction », qui est le processus de mapper des données réelles à ces définitions
• voyant la structure de cette application client-serveur: c'est juste une paire de processus qui se parlent: 'client-serveur' est un mauvais nom, vraiment: il aurait dû être appelé «wallace-gromit» ou «foo-bar», ou philosophes parlant ou autre, mais c'est symétrique: les deux parties sont des pairs.

Comme Jon déjà indiqué, la réduction fonctionne d'une manière paresseuse (alias « appel par le besoin »): take 2 naturals ne serait pas d'abord évaluer l'ensemble complet de Naturals, mais juste prendre le premier et préfixer que pour take 1 (map '\n->n+1' naturals), ce qui réduirait à [1, (1 + 1)] = [1,2].

maintenant la structure de l'application client-serveur est ce (à mes yeux):

• server est un moyen de créer une liste de réponses sur une liste de requêtes en utilisant la fonction process
• client est un moyen de créer une requête basée sur une réponse et d'ajouter la réponse de cette requête à la liste des réponses.

Si vous regardez de près, vous voyez que les deux sont 'un moyen de créer x: xs sur y: ys'. Nous pourrions donc les appeler uniformément wallace et gromit.

Maintenant, il serait facile de comprendre si client serait appelé avec juste une liste de réponses:

someresponses = wallace 0 [1,8,9] -- would reduce to 0,1,8,9 
tworesponses = take 2 someresponses -- [0,1] 

Si les réponses ne sont pas littéralement connues, mais produit par gromit, on peut dire

gromitsfirstgrunt = 0 
otherresponses = wallace gromitsfirstgrunt (gromit otherresponses) 
twootherresponses = take 2 otherresponses -- reduces to [0, take 1 (wallace (gromit ((next 0):...))] 
              -- reduces to [0, take 1 (wallace (gromit (0:...)) ) ] 
              -- reduces to [0, take 1 (wallace (1: gromit (...) ) ) ] 
              -- reduces to [0, take 1 (1 : wallace (gromit (...) )) ] 
              -- reduces to [0, 1 ] 

L'un des deux homologues doit "démarrer" la discussion, d'où la valeur initiale fournie à wallace.Notez également le ~ devant le modèle de gromit: cela indique à Haskell que le contenu de l'argument de liste n'a pas besoin d'être réduit - s'il voit que c'est une liste, c'est suffisant. Il y a un bon sujet dans un wikibook on Haskell (cherchez "Lazy Pattern Matching".)

Answer 4

Voir aussi ma réponse à une question sur « Lier la Noeud "here

Answer 5

Cela ressemble à une belle obfuscation. Si vous avez lu précisément, vous l'avez trouvé simple:

ensuite? c'est l'identité

serveur? c'est simplement un processus de carte qui est la carte '\ n-> n + 1'

client? C'est obscur comment écrire 0: client de serveur par ex. 0: carte '\ n-> n + 1' [0: carte '\ n-> n + 1' [0: ...]]