Haskell:修复或不修复

Question

我最近了解到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-version我会解决,反之亦然会创建一个堆栈溢出？

2)处理列表时,有几种解决方案:递归/修复,foldr/foldl/foldl',可能还有别的东西.关于何时使用每种方法,是否有任何一般指导/建议？例如,您是否会使用foldr无限的素数列表重写上面的代码？

可能还有其他重要问题没有在这里讨论.欢迎任何与使用相关的其他评论fix.

Answer 1

通过以明确的fix形式书写可以获得的一点是递归是"开放的".

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允许在语言级别递归的一种方式,但我们可以构建其他更专业的表单.

Answer 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" 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'将正确评估树,因为selfin fromTreeExt'指的是整个函数,包括"Mul"情况.

这里使用这种方法(上面的例子是本文中使用的一个紧密改编的版本).