StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Well let's think about it for a minute. What type does this lambda expression have?</p> <pre><code>(\y f x -> f (y y f) x) </code></pre> <p>Well <code>f</code> is a function <code>(a -> b) -> a -> b</code>, and <code>x</code> is some value <code>b</code>. What does that make <code>y</code>? Well given what we just said about <code>f</code>,</p> <pre><code>(y y f) :: (a -> b) </code></pre> <p>Also, since we are applying this expression to itself, we know that <code>y</code> has the same type as the entire expression. This is the part where I get a little bit stumped.</p> <p>So <code>y</code> is some magical higher-order function. And it takes two functions as input. So it's sort of like <code>y :: f1 -> f2 -> f3</code>. <code>f2</code> has the form of <code>f</code>, and <code>f3</code> has the result type mentioned above.</p> <pre><code>y :: f1 -> ((a -> b) -> a -> b) -> (a -> b) </code></pre> <p>The question is...what is <code>f1</code>? Well, it has to be <em>the same as the type of <code>y</code></em>. Do you see how this is getting beyond the power of Haskell's type system? The type is defined in terms of itself.</p> <pre><code>f1 = f1 -> ((a -> b) -> a -> b) -> (a -> b) </code></pre> <p>If you want a self-contained "one-liner", then take hammar's suggestion instead:</p> <pre><code>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 </code></pre> <p>Although imho if <code>max</code> is allowable, then <code>fix</code> from Data.Function should be allowable as well. Unless you are in some Prelude-only contest.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload