Как работает ключевое слово rec Haskell? - PullRequest
Новая
       9

Как работает ключевое слово rec Haskell?

23 голосов
/ 23 марта 2011

В обозначении стрелка до можно использовать ключевое слово rec для написания рекурсивных определений.Например: 

rec
    name <- function -< input
    input <- otherFunction -< name

Как это можно оценить?Кажется, что это просто войдет в бесконечный цикл или что-то в этом роде.Я знаю, что это относится к комбинатору стрелок цикла, но я тоже не понимаю, как это работает.

РЕДАКТИРОВАТЬ: этот пример полномочий действительно полезен.Как бы вы написали это с записью делать, хотя?Я полагаю, вам нужно будет использовать rec.

Ответы [ 2 ]

23 голосов
/ 23 марта 2011

Этот бит магии работает из-за лени haskells. Как вы, возможно, знаете, Haskell оценивает значение при необходимости, а не при определении. Таким образом, это работает, если вам не нужно вводить значение напрямую или, возможно, позже.

rec реализовано с использованием функции loop ArrowLoop. Это определяется следующим образом: 

class Arrow a => ArrowLoop a where
        loop :: a (b,d) (c,d) -> a b c

instance ArrowLoop (->) where
        loop f b = let (c,d) = f (b,d) in c

Вы можете видеть: Выход просто возвращается как вход. Он будет рассчитан только один раз, потому что Haskell оценит d только тогда, когда это необходимо.

Вот пример того, как напрямую использовать комбинатор loop. Эта функция вычисляет все полномочия своего аргумента: 

powers = loop $ \(x,l) -> (l,x:map(*x)l)

(Вы могли бы также написать это так: powers x = fix $ (x :) . map (*x))

Как это работает? Ну, бесконечный список способностей находится в аргументе l. Оценка выглядит так: 

powers = loop $ \(x,l) -> (l,x:map(*x)l) ==>
powers b = let (c,d) = (\(x,l) -> (l,x:map(*x)l)) (b,d) in c ==>
powers b = let (c,d) = (d,b:map(*b)d) in d ==> -- Now  we apply 2 as an argument
powers 2 = let (c,d) = (d,2:map(*2)d) in d ==>
         = let (c,(2:d)) = (d,2:map(*2)d) in c ==>
         = let (c,(2:4:d)) = ((2:d),2:map(*2)(2:d)) in c ==>
         = let (c,(2:4:8:d)) = ((2:4:d),2:map(*2)(2:4:d)) in  ==> -- and so on
12 голосов
/ 23 марта 2011

Вот реальный пример: 

loop f b = let (c,d) = f (b,d) in c

f (b,d) = (drop (d-2) b, length b)

main = print (loop f "Hello World")

Эта программа выводит "ld".Функция 'loop f' принимает один вход 'b' и создает один выход 'c'.То, что делает «f», это изучение «b» для получения «длины b», которая возвращается в цикл и связывается с «d».

В «цикле» это «d = длина b» подается в'f', где он используется в расчете в выпадающем списке.

Это полезно для таких хитростей, как построение неизменного двусвязного списка (который также может быть круговым).Также полезно обходить один раз «b», чтобы получить аналитическое «d» (например, длину или самый большой элемент) и построить новую структуру «c», которая зависит от «d».Лень избегает необходимости пересекать 'b' дважды.

...