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

Недавно я узнал о Data.Function.fix, и теперь я хочу применять его повсюду. Например, всякий раз, когда я вижу рекурсивную функцию, я хочу "fix" ее. Поэтому в основном мой вопрос - где и когда я должен его использовать.

Чтобы сделать его более конкретным:

1) Предположим, что у меня есть следующий код для факторизации n:

f n = f' n primes
  where
    f' n (p:ps) = ...
    -- if p^2<=n: returns (p,k):f' (n `div` p^k) ps for k = maximum power of p in n
    -- if n<=1: returns []
    -- otherwise: returns [(n,1)]

Если я переписал его в терминах fix, я получу что-то? Потерять что-то? Возможно ли, что путем перезаписи явной рекурсии в fix -версию я разрешу или наоборот создаст переполнение стека?

2) При работе со списками существует несколько решений: рекурсия/исправление, foldr/foldl/foldl 'и, возможно, что-то еще. Есть ли общее руководство/советы по использованию каждого из них? Например, переписываете ли вы вышеуказанный код с помощью foldr над бесконечным списком простых чисел?

Есть, возможно, другие важные вопросы, которые здесь не рассматриваются. Любые дополнительные комментарии, связанные с использованием fix, также приветствуются.

Ответ 1

Одна вещь, которая может быть получена путем написания в явной форме fix ed, заключается в том, что рекурсия остается открытой.

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 эффективно передает функцию как свой первый аргумент. Однако, оставляя рекурсию открытой, мы можем изменить, какая функция получает "прошло назад". Лучшим примером использования этого свойства является использование memoFix из пакета memoize.

factM :: Integer -> Integer
factM = memoFix factOpen

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

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

Ответ 2

Я хотел бы упомянуть еще одно использование 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" ab] не будет работать, так как оригинал 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".

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

Ответ 3

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

Связки Haskell let и where являются рекурсивными: одно имя на 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 ()).

См. также:

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

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

Ответ 4

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 []

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