[Haskell-beginners] A Week in and Clueless

[Ertugrul Söylemez]

Philip Cote <cotejrp at gmail.com> wrote:

> So a week into Haskell, I still seem to be not “getting” it which is
> kind of weird in my case. I came in with knowledge of a lot of
> functional ideas from using them in Javascript and Python.  Or at
> least I thought I knew them.
>
> 5 chapters into "Learn You a Haskell", I admit it's not really sinking
> in for me even after typing in and running all the examples.  I
> acknowledge that I don't know jack.

This is going to be a somewhat long mail, in which I'm attempting to
give you an introduction of my own.  Be brave and read it. =)

Well, despite popular belief JavaScript and Python are not anywhere near
functional.  JS just uses callbacks and passes them around through
higher order functions, but that's just the regular event-handling
imperative style.  There is really nothing functional about that.

Functional style in JS starts when you start using things like 'each'
from jQuery, i.e. you're not just defining event handlers.  You are
actually passing /behavior/ to a function.  This is basically what a
functional language takes to its conclusion.  You have an action (like
putStrLn "Hello world"), and you want to perform it n times.  Let me
give this example in both JavaScript and Haskell:

    function timesHello(n) {
        while (n > 0) {
            print("Hello world");
            n--;
        }
    }

    timesHello 0 = return ()
    timesHello n = putStrLn "Hello world" >> nTimes (n - 1)

But why should we be constrained to printing hello world?  On the other
hand, how could we abstract it?  The complicated answer is to use a
complicated OO solution, but functional programmers can do a lot better:

    function times(n, action) {
        while (n > 0) {
            action();
            n--;
        }
    }

    times 0 action = return ()
    times n action = action >> times (n - 1) action

Unfortunately JavaScript has quite a heavy syntax for anonymous
functions, which makes this style a lot less useful:

    times(3, function() { print("Hello world"); });

But in Haskell we can write this elegantly:

    3 `times` putStrLn "Hello world"

This is the very fundamental idea.  Since Haskell programs are lazily
evaluated you can stretch this idea to entirely new dimensions, where
the line between data and control structures disappears.  A common
statement is that lists in Haskell correspond to 'for' loops in other
languages, which is quite true, but can only be seen when you ask
yourself, "how would I solve this?".

Let me give you an example:  You are searching for the smallest square
natural number that has a digit sum greater than 20.  First we need a
function to calculate digit sums.  This would be a 'for' loop in an
imperative language, wouldn't it?  In Haskell we do something different:
Our function starts iterating division by 10:

    digitSum = iterate (`div` 10)
    digitSum 357 = [357, 35, 3, 0, 0, 0, ...

Then we want to get rid of the zeroes.  Starting with the first zero all
following numbers will be zeroes, so we stop before the first zero:

    digitSum = takeWhile (> 0) . iterate (`div` 10)
    digitSum 357 = [357, 35, 3]

As you can see we have already used two higher order functions that take
behavior as arguments.  Next we need to take everything modulo 10:

    digitSum = map (`mod` 10) . takeWhile (> 0) . iterate (`div` 10)
    digitSum 357 = [7, 5, 3]

Finally we take the sum:

    digitSum = sum . map (`mod` 10) . takeWhile (> 0) . iterate (`div` 10)
    digitSum 357 = 15

Ok, let's solve the original problem.  Again this would be another 'for'
loop in other languages, but there is a Haskell solution as well:  The
smallest square natural number...  "smallest natural" sounds a lot like
we want to search from 0 upwards, so let's just capture our search space
as a list:

    [0..] = [0, 1, 2, 3, 4, ...

But we want squares:

    map (^2) [0..] = [0, 1, 4, 9, 16, ...

And we want only the numbers with a digit sum greater than 20:

    filter (\x -> digitSum x > 20) . map (^2) $ [0..]

The natural number 44944 is a square, and its digit sum is greater than
20, so this list is certainly nonempty.  So there must be a smallest
number in that list, which will be just the first entry, because the
list is sorted by construction.  In other words, it's safe to use
'head':

    head . filter (\x -> digitSum x > 20) . map (^2) $ [0..]

And that gives us the solution 1849, which has a digit sum of 22 and
meets our specification.


> Any ideas or exercises that might help me along?

Yes.  Pick a small task and solve it.  Write code.  If you get stuck,
just visit us at #haskell on Freenode or ask here.

I hope this helped.


Greets,
Ertugrul

-- 
Not to be or to be and (not to be or to be and (not to be or to be and
(not to be or to be and ... that is the list monad.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/beginners/attachments/20130111/c845b7dc/attachment.pgp>