[Haskell-cafe] Re: flip fix and iterate

[Claus Reinke]

> Haskell has a way of making one feel dumb.  This is by far the most
> challenging programming language I've ever used.

i wouldn't see either as a particularly positive attribute. a language should enable,
explain, encourage, and perhaps inspire. if it also leaves you feeling that you could
do more and go further should you ever want or need to, that's okay, too.

but (unless designed for such purpose;) a language should not be a puzzle, nor
an obstacle, nor should its users feel judged or needlessly challenged.

http://www.cs.utexas.edu/~EWD/transcriptions/EWD03xx/EWD340.html

of course, all of that also depends on not only on the language, but on how it is 
used, presented, and perceived.  haskell allows for a wide variety of approaches 
to programming, allowing programmers to be productive in plain old functional 
programming, or perhaps seemingly less so in advanced pointless type-level
meta-programming. that doesn't mean that either approach is better or worse 
than the other, or that one approach fits all problems, or programmers. even 
one's measures of what constitutes simple code can evolve over time.

so, by picking those techniques that work for you, and keeping an eye open for
those that you're not (yet) comfortable with, you seem to be on the right track.

perhaps other techniques will make more sense to you later, or you'll find the
need to overcome limitations in the techniques you use now (which is how most
of the more complicated-looking themes have developed from easier-looking
ones in the past), perhaps not. understanding more advanced haskell tricks can
be fun, but for most programmers, the point is not (just:) to engage in intellectual
games and challenges for their own sake, but in exploring what their current
understanding of haskell does or does not allow them to do.

> I won't try to understand fix just yet, but I'm still confused by the type of fix:
> 
>     fix :: (a -> a) -> a
> 
> It appears to me that it takes a function as an argument, and that
> function takes a single argument.  So how are you passing fix an
> anonymous function taking 2 arguments?  Sorry if I have beaten this
> horse to death, but my pea-sized brain is working overtime here.

fix takes a function as an argument, and that function takes a single argument.
that function also returns something of the same type as its single argument.
which is where things get more interesting/complicated. but first:

lets give the argument of fix a name and its type: f :: a -> a

so fix takes f and produces an a, but where can that a come from?

that a could be the result of f, but then we'd need something of type a to put
into f. so, once again, we need an a. where could this a come from (i'm not a
language, so i feel free to pose challenging puzzles;-)?

hint: the relevant equation for fix is

     fix f = f (fix f)    -- (1)

read from right to left, we can see that f applied to (fix f) returns (fix f), which 
is why (fix f) is called a fixed point of f (and fix the fixed-point combinator).

read from left to right, we can see how fix accomplishes the feat of computing
a fixed point for any function f :: a -> a we might pass in as a parameter - it 
applies f to the fixed point yet to be computed, which unfolds to:

    fix f = f (f (..... f (fix f)..)..)

so, f gets applied to a copy of itself, applied to a copy of itself, applied to ..
in other words, fix f recursively creates a supply of copies of f, which f can
make use of in its definition. lets say f = \self-> .. self .., then

    fix (\self-> .. self ..) 
    = (\self-> .. self ..) (fix (\self-> .. self ..))    -- by (1)
    = .. (fix (\self-> .. self ..)) ..     -- reduce and substitute for self
    = .. ((\self-> .. self ..) (fix (\self-> .. self ..))) ..     -- by (1)
    
so, fix f supplies f with copies to use for recursive calls within its body, and 
that a type is really the type of the body of f, as well as that of the self-reference.

which brings us to that extra challenge of extra parameters. so far, f is a function
only so that its body can take in a self-reference, and fix f corresponds to a 
recursive variable definition. if we want to define a recursive function instead,
we need more parameters. lets say f = \self-> \x-> .. (self x) .., then

    fix (\self->\x-> .. (self x) ..) 
    = (\self->\x-> .. (self x) ..) (fix (\self->\x-> .. (self x) ..))
    = \x->.. ((fix (\self->\x-> .. (self x)..)) x) .. 
    = \x->.. (((\self->\x-> .. (self x)..) (fix (\self->\x-> .. (self x) ..))) x).. 

(it really helps to perform the reductions yourself, rather than read them, btw)

and what has happened to the type of f? f takes a self-reference, and returns a
function of one argument, so 

    f :: ?? -> (b->c)

and the type of the self-reference is the type of f's body, so

    f :: (b->c) -> (b->c)

or

    f :: (b->c) -> b -> c

from which we can see that the type of fix gets instantiated to

    fix :: ((b -> c) -> (b -> c)) -> (b -> c)

or 

    fix :: ((b -> c) -> (b -> c)) -> b -> c

and suddenly, fix does have two parameters, which flip can flip!-)

no magic, just technology sufficiently advanced to be indistinguishable from it:
a function of one parameter, which returns a function of one parameter, is a
function of more than one parameter.

at which point this particular fixed-point combinator puts its recursive 
unfoldings to rest for tonight.

hth,
claus