Haskell: исправлять или не исправлять

Одна вещь, которую можно получить, написав в явно fixed форме, - это оставить рекурсию «открытой».

factOpen :: (Integer -> Integer) -> Integer -> Integer
factOpen recur 0 = 1
factOpen recur n = n * recur (pred n)

Мы можем использовать fix, чтобы регулярно fact возвращаться

fact :: Integer -> Integer
fact = fix factOpen

Это работает, потому что fix эффективно передает саму функцию в качестве первого аргумента. Однако, оставив рекурсию открытой, мы можем изменить, какая функция будет «передана обратно». Лучшим примером использования этого свойства является использование чего-то вроде _ 7_ из memoize пакета.

factM :: Integer -> Integer
factM = memoFix factOpen

И теперь factM имеет встроенную память.

Фактически, у нас есть рекурсия открытого стиля, которая требует, чтобы мы вменяли рекурсивный бит как вещь первого порядка. Рекурсивные привязки - это один из способов, которым Haskell допускает рекурсию на уровне языка, но мы можем создавать и другие, более специализированные формы.

Я хотел бы упомянуть еще одно использование fix; Предположим, у вас есть простой язык, состоящий из литералов сложения, отрицательных и целых чисел. Возможно, вы написали синтаксический анализатор, который принимает String и выводит Tree:

data Tree = Leaf String | Node String [Tree]
parse :: String -> Tree

-- parse "-(1+2)" == Node "Neg" [Node "Add" [Node "Lit" [Leaf "1"], Node "Lit" [Leaf "2"]]]

Теперь вы хотите оценить свое дерево до единственного целого числа:

fromTree (Node "Lit" [Leaf n]) = case reads n of {[(x,"")] -> Just x; _ -> Nothing}
fromTree (Node "Neg" [e])      = liftM negate (fromTree e) 
fromTree (Node "Add" [e1,e2])  = liftM2 (+) (fromTree e1) (fromTree e2)

Предположим, кто-то другой решил расширить язык; они хотят добавить умножение. Им потребуется доступ к исходному коду. Они могли попробовать следующее:

fromTree' (Node "Mul" [e1, e2]) = ...
fromTree' e                     = fromTree e

Но тогда Mul может появиться только один раз, на верхнем уровне выражения, поскольку вызов fromTree не будет знать о случае Node "Mul". Tree "Neg" [Tree "Mul" a b] не будет работать, поскольку исходный fromTree не имеет шаблона для "Mul". Однако, если та же функция написана с использованием fix:

fromTreeExt :: (Tree -> Maybe Int) -> (Tree -> Maybe Int)
fromTreeExt self (Node "Neg" [e]) = liftM negate (self e)
fromTreeExt .... -- other cases

fromTree = fix fromTreeExt

Тогда возможно расширение языка:

fromTreeExt' self (Node "Mul" [e1, e2]) = ...
fromTreeExt' self e                     = fromTreeExt self e

fromTree' = fix fromTreeExt'

Теперь расширенный fromTree' будет правильно оценивать дерево, поскольку self в fromTreeExt' относится ко всей функции, включая случай "Mul".

Этот подход используется здесь (приведенный выше пример представляет собой адаптированную версию использования в статье).

Обратите внимание на разницу между _Y f = f (_Y f) (рекурсия, значение - копирование) и fix f = x where x = f x (corecursion, ссылка - совместное использование).

Привязки let и where Haskell рекурсивны: одно и то же имя на LHS и RHS относится к одному и тому же объекту. Ссылка является общедоступной.

В определении _Y нет совместного использования (если компилятор не выполняет агрессивную оптимизацию исключения общих подвыражений). Это означает, что он описывает рекурсию, где повторение достигается путем применения копии оригинала, как в классической метафоре рекурсивная функция, создающая свои собственные копии. Corecursion, с другой стороны, полагается на совместное использование, на ссылку на одну и ту же сущность.

Пример, простые числа, вычисленные

2 : _Y ((3:) . gaps 5 . _U . map (\p-> [p*p, p*p+2*p..]))

-- gaps 5 == ([5,7..] \\)
-- _U     == sort . concat

либо повторно использовать свой собственный вывод (с fix, let g = ((3:)...) ; ps = g ps in 2 : ps), либо создать отдельный источник простых чисел для себя (с _Y, let g () = ((3:)...) (g ()) in 2 : g ()).

Смотрите также:

• двойной поток потока для предотвращения ненужной мемоизации?
• Как реализовать эффективный бесконечный генератор простых чисел в Python?

Или, используя обычный пример факториальной функции,

gen rec n = n<2 -> 1 ; n * rec (n-1)            -- "if" notation

facrec   = _Y gen 
facrec 4 = gen (_Y gen) 4 
         = let {rec=_Y gen} in (\n-> ...) 4
         = let {rec=_Y gen} in (4<2 -> 1 ; 4*rec 3)
         = 4*_Y gen 3
         = 4*gen (_Y gen) 3
         = 4*let {rec2=_Y gen} in (3<2 -> 1 ; 3*rec2 2) 
         = 4*3*_Y gen 2                         -- (_Y gen) recalculated
         .....

fac      = fix gen 
fac 4    = (let f = gen f in f) 4             
         = (let f = (let {rec=f} in (\n-> ...)) in f) 4
         = let {rec=f} in (4<2 -> 1 ; 4*rec 3)  -- f binding is created
         = 4*f 3
         = 4*let {rec=f} in (3<2 -> 1 ; 3*rec 2)  
         = 4*3*f 2                              -- f binding is reused
         .....

1) fix - это просто функция, она улучшает ваш код, когда вы используете рекурсию. Это делает ваш код красивее. Например, посетите страницу Haskell Wikibook - Исправление и рекурсия.

2) Вы знаете, что такое foldr? Похоже, что foldr бесполезна при факторизации (или я не понял, что вы имеете в виду). Вот простое разложение без исправления:

fact xs = map (\x->takeWhile (\y->y/=[]) x) . map (\x->factIt x) $ xs
 where factIt n = map (\x->getFact x n []) [2..n]
   getFact i n xs
    | n `mod` i == 0 = getFact i (div n i) xs++[i]
    | otherwise      = xs

и с исправлением (это работает точно так же, как и предыдущее):

fact xs = map (\x->takeWhile (\y->y/=[]) x) . map (\x->getfact x) $ xs
  where getfact n  = map (\x->defact x n) [2..n]
       defact i n  = 
        fix (\rec j k xs->if(mod k j == 0)then (rec j (div k j) xs++[j]) else xs ) i n []

Это некрасиво, потому что в данном случае исправление - не лучший выбор (но всегда есть кто-то, кто может написать его лучше).