Взаимная рекурсия - может кто-нибудь помочь объяснить, как работает этот код?

Question

Я читаю «Нежное введение в Haskell», и в начале он использует этот пример, который прекрасно работает в GHC и ужасно в моем мозгу:

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

И телефонный код:
take 10 reqs

Как я вижу, вызывается reqs, что приводит к вызову client с аргументами 0 и resps. Таким образом, resps теперь не нужно вызывать ... который, в свою очередь, снова вызывает reqs? Все это кажется таким бесконечным ... если бы кто-то мог подробно рассказать, как это на самом деле работает, я был бы очень признателен!

Answer 1

Я считаю, что, как правило, стоит отрабатывать поведение небольших программ на Haskell вручную. Правила оценки довольно просты. Главное, что нужно помнить, это то, что Haskell не строгий (он же lazy ): выражения оцениваются только при необходимости. Лень является причиной, по-видимому, бесконечных определений, которые могут дать полезные результаты. В этом случае использование take означает, что нам понадобятся только первые 10 элементов бесконечного списка reqs: они все, что нам «нужно».

С практической точки зрения, «потребность», как правило, обусловлена ​​сопоставлением с образцом. Например, выражение списка, как правило, будет оцениваться до того момента, когда мы сможем различить [] и (x:xs) до применения функции. (Обратите внимание, что '~', предшествующий шаблону, как в определении client, делает его ленивым (или неопровержимым ): ленивый шаблон не будет принудительно аргументировать свой аргумент, пока все выражение не будет принудительный.)

Помня, что take это:

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

Оценка take 10 reqs выглядит так:

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

Понимание этого кода требует двух навыков:

• различение между «определением», которое может быть бесконечным (например, набор натуральных чисел: naturals = (1 : map '\n->n+1' naturals) или список обработанных запросов) и «сокращением», которое представляет собой процесс сопоставления фактических данных с этими определениями
• видя структуру этого клиент-серверного приложения: это просто пара процессов, говорящих друг с другом: на самом деле «клиент-сервер» - это плохое имя: его следовало называть «wallace-gromit» или «foo-bar» ', или говорят философы или что-то еще, но это симметрично: обе стороны равны.

Как уже говорил Джон , сокращение работает ленивым способом (иначе называемый «вызов по необходимости»): take 2 naturals не будет сначала оценивать полный набор натуральных чисел, а просто возьмет первый и добавьте это к take 1 (map '\n->n+1' naturals), которое уменьшится до [1, (1 + 1)] = [1,2].

Теперь структура клиент-серверного приложения такова (на мой взгляд):

• server - это способ создать список ответов из списка запросов с помощью функции process
• client - это способ создания запроса на основе ответа и добавления ответа этого запроса в список ответов.

Если вы присмотритесь, вы увидите, что оба являются «способом создания x: xs из y: ys». Таким образом, мы могли бы равномерно назвать их wallace и gromit.

Теперь было бы легко понять, если бы client вызывался только со списком ответов:

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

Если ответы не известны буквально, но производятся gromit, мы можем сказать

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 ]

Один из обоих пиров должен «начать» обсуждение, поэтому начальное значение предоставлено wallace.

Также обратите внимание на шаблон ~ before gromit: это говорит Haskell, что содержимое аргумента list не нужно сокращать - если он видит, что это список, этого достаточно. Об этом есть хорошая тема в вики-книге на Haskell (ищите "Lazy Pattern Matching).

Answer 3

Прошло много времени с тех пор, как я играл с Haskell, но я уверен, что он лениво оценивается, то есть он рассчитывает только то, что ему действительно нужно. Таким образом, хотя reqs бесконечно рекурсивен, поскольку для take 10 reqs нужны только первые 10 возвращаемых элементов списка, то есть все, что на самом деле рассчитывается.

Answer 4

См. Также мой ответ на вопрос о "Связывая узел" здесь

Answer 5

Похоже, хорошее запутывание. Если вы прочитали точно, вы нашли это просто:

дальше? это личность

Сервер? это просто процесс карты, который является картой '\ n-> n + 1'

клиент? Это непонятный способ, как написать 0: серверный клиент, например 0: карта '\ n-> n + 1' [0: карта '\ n-> n + 1' [0: ...]]