Y combinator、Haskell中的无限类型和匿名递归

Question

我正在尝试解决最大子序列和问题，并想出了一个聪明的解决方案。

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中，如果你足够坚持，你可以在一行上编写整个程序，以真正说明一个程序实际上只是一个大表达式。因此，我想尝试消除额外的挑战。

现在，我遇到了经典问题：如何进行匿名递归？当您无法给函数命名时，如何进行递归？幸运的是，计算机之父们早在很久以前就解决了这个问题，他们发现了固定点组合器，其中最流行的是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)

仅仅给出

Prelude> :l C:\maxsubseq.hs
[1 of 1] Compiling Main             ( C:\maxsubseq.hs, interpreted )

C:\maxsubseq.hs:10:29:
    Occurs check: cannot construct the infinite type:
      t0 = t0 -> (([Int] -> Int) -> [Int] -> Int) -> [Int] -> Int
    In the first argument of `y', namely `y'
    In the first argument of `f', namely `(y y f)'
    In the expression: f (y y f) x

C:\maxsubseq.hs:11:29:
    Occurs check: cannot construct the infinite type:
      t0 = t0 -> (([Int] -> Int) -> [Int] -> Int) -> [Int] -> Int
    In the first argument of `y', namely `y'
    In the first argument of `f', namely `(y y f)'
    In the expression: f (y y f) x

C:\maxsubseq.hs:12:14:
    The lambda expression `\ g' gmax lmax list -> ...'
    has four arguments,
    but its type `([Int] -> Int) -> [Int] -> Int' has only two
    In the second argument of `\ y f x -> f (y y f) x', namely
      `(\ g' gmax lmax list
          -> if list == [] then
                 gmax
             else
                 g' (max gmax lmax + head list) (max 0 lmax + head list) tail list)'
    In the expression:
      (\ 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)
    In an equation for `msss'':
        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)
Failed, modules loaded: none.

从f (y y f)改为f (y f)只会得到

C:\maxsubseq.hs:11:29:
    Couldn't match expected type `[Int] -> Int'
                with actual type `[Int]'
    Expected type: (([Int] -> Int) -> t1 -> t0) -> t2 -> t0
      Actual type: ([Int] -> Int) -> t1 -> t0
    In the first argument of `y', namely `f'
    In the first argument of `f', namely `(y f)'
Failed, modules loaded: none.

我尝试采用不同的方法，仅在外部定义组合器，然而这仍然无法工作，并且并不真正满足我在一个表达式中完成它的挑战。

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演算不一致的悖论有关。但我不确定。如果有人能澄清一下就好了。

此外，我认为递归总是可以用fold函数表示的。有人能向我展示如何只使用fold来实现递归吗？但要求代码仍然是单个表达式。

- TheIronKnuckle

---

第二个定义有什么问题（其中y组合子是单独定义的）？你只需要更正类型定义或在末尾添加0 0即可。 - is7s

Answer 1

在Haskell中不能像那样定义Y组合子。正如你所注意到的，会导致一个无限类型。幸运的是，在Data.Function中已经有了它，作为fix，它是使用let绑定来定义的：

fix f = let x = f x in x

- hammar

---

肯定有一种方法可以在Haskell中内联定义和使用Y组合器。 - TheIronKnuckle

可以使用newtype关键字实现该功能。@TheIronKnuckle在此提供了相关的解释和代码示例，详见链接：https://dev59.com/4G855IYBdhLWcg3wjlGL#5885270。 - hammar

@TheIronKnuckle：当然，只需将fix的定义内联即可：(\f -> let x = f x in x)。 - opqdonut

Answer 2

因为Y组合子需要无限类型，所以您需要像这样的解决方法。

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

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

- Sjoerd Visscher

---

请注意，无限类型仅出现在Haskell类型系统的弱子集中，例如System F，它缺乏递归let和递归类型。 - nponeccop

Answer 3

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

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

好的，f是一个函数(a -> b) -> a -> 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)

如果您想要一个自包含的“一行代码”，那么请采用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的比赛。

- Dan Burton