19

我最近了解了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也欢迎与使用相关的任何其他评论。

4

4 回答 4

19

通过以明确编辑的形式编写可以获得的一件事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有效地将函数本身作为其第一个参数传递。然而，通过保持递归打开，我们可以修改哪个函数被“传回”。使用此属性的最佳示例是使用类似memoFixfrom memoizepackage的东西。

factM :: Integer -> Integer
factM = memoFix factOpen

现在factM有内置的记忆。

实际上，我们有开放式递归要求我们将递归位归为一阶事物。递归绑定是 Haskell 允许在语言级别进行递归的一种方式，但我们可以构建其他更专业的形式。

于 2014-02-10T21:35:54.950 回答
7

我想提一下 ; 的另一种用法fix。假设您有一种由加法、负数和整数文字组成的简单语言。也许您已经编写了一个解析器，它接受 aString并输出 a 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

但是 thenMul只能出现一次，在表达式的顶层，因为调用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'

现在，extendedfromTree'将正确评估树，因为selfinfromTreeExt'指的是整个函数，包括“Mul”案例。

这里使用了这种方法（上面的例子是论文中使用的一个紧密改编的版本）。

于 2014-02-11T03:33:57.207 回答
2

注意_Y f = f (_Y f)（递归，值--复制）和fix f = x where x = f x（核心递归，引用--共享）之间的区别。

Haskelllet和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
         .....
于 2014-02-12T06:48:35.767 回答
1

1) fix 只是一个函数，当你使用一些递归时它会改进你的代码。它使您的代码更漂亮。例如使用访问：Haskell Wikibook - Fix and recursion。

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

这并不漂亮，因为在这种情况下修复不是一个好的选择（但总有人可以写得更好）。

于 2014-02-10T22:23:14.107 回答