Haskell 中的 Y 组合器、无限类型和匿名递归

Question

我试图解决最大子序列和问题并提出了一个neato解决方案

msss :: (Ord a, Num a) => [a] -> a
msss = f 0 0

f gmax _ [] = gmax
f gmax lmax (x:xs) = 
  let g = max (lmax + x)
  in  f (g gmax) (g 0) xs

你调用包装函数msss，然后调用 f，后者又实际完成工作。 该解决方案很好并且工作正常。如果由于某种原因我必须解决生产代码中的最大子序列和问题，我就会这样做。

然而，这个包装函数确实让我烦恼。我喜欢在 Haskell 中，如果你有足够的毅力，你可以在一行上编写整个程序，真正让人们明白程序几乎只是一个大表达式。所以我想我应该尝试消除包装函数来应对额外的挑战。

现在我遇到了经典问题：如何进行匿名递归？当你无法给函数命名时，你如何进行递归？值得庆幸的是，计算之父很久以前就通过发现定点组合器解决了这个问题，其中最流行的是< a href="http://en.wikipedia.org/wiki/Fixed-point_combinator#Y_combinator">Y 组合器。

我已经进行了各种尝试来设置 Y 组合器，但它们无法通过编译器。

msss' :: [Int] -> Int
msss' = (\y f x -> f (y y f) x) 
        (\y f x -> f (y y f) x) 
        (\g' gmax lmax list -> if list == [] 
                               then gmax 
                               else g' (max gmax lmax + head list) 
                                       (max 0    lmax + head list) 
                                       tail list)

只是给出

前奏> :l C:\maxsubseq.hs
[1 of 1] 编译 Main（C:\maxsubseq.hs，已解释）

C:\maxsubseq.hs:10:29:
    发生检查：无法构造无限类型：
      t0=t0→ (([Int] -> Int) -> [Int] -> Int) -> [Int]-> INT
    在‘y’的第一个参数中，即‘y’
    在‘f’的第一个参数中，即‘(yyf)’
    表达式中：f(yyf)x

C:\maxsubseq.hs:11:29:
    发生检查：无法构造无限类型：
      t0=t0→ (([Int] -> Int) -> [Int] -> Int) -> [Int]-> INT
    在‘y’的第一个参数中，即‘y’
    在‘f’的第一个参数中，即‘(yyf)’
    表达式中：f(yyf)x

C:\maxsubseq.hs:12:14:
    lambda 表达式 `\g' gmax lmax list -> ...'
    有四个参数，
    但它的类型 `([Int] -> Int) -> [Int]-> Int'只有两个
    在 `\ yfx -> 的第二个参数中f(yyf)x'，即
      `(\g' gmax lmax 列表
          ->如果列表 == [] 那么
                 最大加速度
             别的
                 g' (max gmax lmax + head list) (max 0 lmax + head list) tail list)'
    表达式中：
      (\ yfx -> f (yyf) x)
        (\ yfx -> f (yyf) x)
        (\ g' gmax lmax 列表
           ->如果列表 == [] 那么
                  最大加速度
              别的
                  g' (max gmax lmax + head list) (max 0 lmax + head list) tail list)
    在“msss”的等式中：
        女士
          = (\ yfx -> f (yyf) x)
              (\ yfx -> f (yyf) x)
              (\ g' gmax lmax 列表
                 ->如果列表 == [] 那么
                        最大加速度
                    别的
                        g' (max gmax lmax + head list) (max 0 lmax + head list) tail list)
失败，已加载模块：无。

从 f (yyf) 更改为 f (yf) 只是给出

<前><代码>C:\maxsubseq.hs:11:29: 无法匹配预期类型 `[Int] ->国际' 与实际类型“[Int]” 预期类型：(([Int] -> Int) -> t1 -> t0) -> t2-> t0 实际类型：([Int] -> Int) -> t1-> t0 在‘y’的第一个参数中，即‘f’ 在‘f’的第一个参数中，即‘(yf)’ 失败，已加载模块：无。

我尝试通过在外部定义组合器来采取不同的方法，但这仍然不起作用，并且不能真正满足我在一个表达式中实现这一目标的挑战。

y f = f (y f)

msss' :: [Int] -> Int
msss' = y (\g' gmax lmax list -> if list == [] 
                                 then gmax 
                                 else g' (max gmax lmax + head list) 
                                         (max 0    lmax + head list) 
                                         tail list)

你能发现我所做的事情有什么问题吗？我不知所措。关于构造无限类型的抱怨真的让我很恼火，因为我认为 Haskell 就是关于这类事情的。它有无限的数据结构，那么为什么会出现无限类型的问题呢？我怀疑这与显示非类型化 lambda 演算不一致的悖论有关。但我不确定。如果有人能澄清一下就好了。

另外，我的印象是递归总是可以用折叠函数来表示。谁能告诉我如何仅使用折叠来做到这一点？但代码必须是单个表达式的要求仍然存在。

Answer 1

你不能像 Haskell 中那样定义 Y 组合器。正如您所注意到的，这会产生无限类型。幸运的是，它已经在 Data.Function 中作为 fix 使用，它是使用 let 绑定定义的：

fix f = let x = f x in x

Answer 2

由于 Y 组合器需要无限类型，因此您需要像这样的解决方法。

但我会将您的 msss 函数写成这样的单行代码：

msss = fst . foldr (\x (gmax, lmax) -> let g = max (lmax + x) in (g gmax, g 0)) (0, 0)

Answer 3

好吧，让我们考虑一下。这个 lambda 表达式是什么类型？

(\y f x -> f (y y f) x)

那么 f 是一个函数 (a -> b) ->一个-> b，而x是某个值b。 y 是什么意思？考虑到我们刚才所说的 f，

(y y f) :: (a -> b)

而且，由于我们将此表达式应用于自身，我们知道 y 与整个表达式具有相同的类型。这是我有点困惑的部分。

所以 y 是一些神奇的高阶函数。它需要两个函数作为输入。所以它有点像 y :: f1 -> f2-> f3。 f2 具有 f 的形式，f3 具有上面提到的结果类型。

y :: f1 -> ((a -> b) -> a -> b) -> (a -> b)

问题是...f1 是什么？嗯，它必须与 y 的类型相同。您是否看到这如何超出了 Haskell 类型系统的能力？该类型是根据其自身定义的。

f1 = f1 -> ((a -> b) -> a -> b) -> (a -> b)

如果您想要一个独立的“one-liner”，那么请采用 hammar 的建议：

msss' = (\f -> let x = f x in x) 
        (\g' gmax lmax list -> case list of
            [] -> gmax
            (x:xs) -> g' (max gmax lmax + x) (max 0 lmax + x) xs
        ) 0 0

尽管恕我直言，如果 max 是允许的，那么 Data.Function 中的 fix 应该是允许的，因为出色地。除非你参加一些只有 Prelude 的比赛。