Y combinator, Infinite types and Anonymous recursion in Haskell

Question

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.

Stafani

What's wrong with the second definition (in which the y-combinator is defined separately)? you just need to correct the type definition or add 0 0 at the end – Wingate

Answer 1

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

Mella

Surely there is SOME way to define + use the Y combinator inline in haskell – Stafani

@TheIronKnuckle: It's possible if you introduce a newtype. – Mella

@TheIronKnuckle: Sure, just inline the definition of fix: (\f -> let x = f x in x) – Affecting

Answer 2

Because the Y combinator needs infinite types, you'll need workarounds like this one.

But I'd write your msss function as a one-liner like this:

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

Vyatka

Note that infinite types appear only in weak subsets of Haskell type systems such as System F, which lacks both recursive lets and recursive types. – Gorged

Answer 3

Well let's think about it for a minute. What type does this lambda expression have?

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

Well f is a function (a -> b) -> a -> b, and x is some value b. What does that make y? Well given what we just said about f,

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

Also, since we are applying this expression to itself, we know that y has the same type as the entire expression. This is the part where I get a little bit stumped.

So y is some magical higher-order function. And it takes two functions as input. So it's sort of like y :: f1 -> f2 -> f3. f2 has the form of f, and f3 has the result type mentioned above.

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

The question is...what is f1? Well, it has to be the same as the type of y. Do you see how this is getting beyond the power of Haskell's type system? The type is defined in terms of itself.

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

If you want a self-contained "one-liner", then take hammar's suggestion instead:

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

Although imho if max is allowable, then fix from Data.Function should be allowable as well. Unless you are in some Prelude-only contest.

Tiga