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

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

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

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

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

Ответы

Ответ 1

Этот бит волшебства работает из-за хэскелов лень. Как вы, возможно, знаете, 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

Ответ 2

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

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" .

В 'loop' эта 'd = длина b' подается в 'f', где она используется при вычислении в drop.

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