[SOLVED] Y combinator, Infinite types and Anonymous recursion in Haskell

Y combinator, Infinite types and Anonymous recursion in Haskell

I was trying to solve the maximal subsequence sum problem and came up with a neato solution

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

You call the wrapper function msss, which then calls f, which in turn actually does the work. The solution is good and afaik working correctly. If for some reason I had to solve the maximal subsequence sum problem in production code, that is how I would do it.

However that wrapper function really bugs me. I love it how in haskell, if you are persistent enough you can write your entire program on a single line, to truly drive home the point that a program is pretty much just one big expression. So I figured I'd try and eliminate the wrapper function for the extra challenge.

It's now I run into the classic problem: How to do anonymous recursion? How do you do recursion when you can't give names to functions? Thankfully the fathers of computing solved this problem ages ago by discovering Fixed-Point Combinators, with the most popular being the Y Combinator.

I've made various attempts to get a Y combinator set up, but they can't get past the compiler.

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)

just gives

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.

Changing from f (y y f) to f (y f) just gives

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.

I've tried taking a different approach by just defining the combinator externally, however this still isn't working and doesn't really meet my challenge to do it in one expression.

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)

Can you spot what's wrong with what I'm doing? I'm at a loss. The complaining about constructing infinite types really ticks me off because I though Haskell was all about that sort of thing. It has infinite data structures, so why the problem with infinite types? I suspect it has something to do with that paradox which showed untyped lambda calculus is inconsistent. I'm not sure though. Would be good if someone could clarify.

Also, I'm under the impression that recursion can always be represented with the fold functions. Can anyone show me how I could do it by just using a fold? The requirement that the code be a single expression still stands though.

Solution

You cannot define the Y combinator like that in Haskell. As you noticed, that results in an infinite type. Fortunately, it is already available in Data.Function as fix, where it's defined using a let binding:

fix f = let x = f x in x