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

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该函数,然后实际执行该工作.解决方案很好,afaik工作正常.如果由于某种原因我必须解决生产代码中的最大子序列和问题,那就是我会这样做的.

然而,包装函数确实让我感到困惑.我喜欢它如何在haskell中,如果你足够坚持,你可以将你的整个程序写在一条线上,真正让家庭认为程序几乎只是一个大表达.所以我想我会尝试消除额外挑战的包装函数.

现在我遇到了经典问题:如何进行匿名递归？当你不能给函数命名时,你如何做递归？值得庆幸的是,计算机的父亲在很久以前通过发现定点组合器来解决这个问题,其中最受欢迎的是Y Combinator.

我已经做了各种尝试来设置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演算是不一致的.我不确定.如果有人能澄清,那就好了.

此外,我的印象是递归始终可以用折叠函数表示.任何人都可以告诉我如何通过使用折叠来做到这一点？代码是单个表达式的要求仍然存在.

Answer 1

您无法在Haskell中定义Y组合器.正如您所注意到的那样,这会导致无限类型.幸运的是,它已经在Data.Functionas中使用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) -> 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

虽然imho if max是允许的,但是fix从Data.Function也应该是允许的.除非你参加一些Prelude-only比赛.