[Haskell-beginners] How to think like a functional programmer?

[Ertugrul Soeylemez]

"Costello, Roger L." <costello at mitre.org> wrote:

> I am working on a project and am trying hard to write the code in a
> functional style.
>
> Sadly, upon reviewing what I've written, I realize that I am not
> succeeding. I just devised a recipe for solving the problem and then
> created functions corresponding to steps in the recipe.  I am still
> thinking imperatively, not functionally.
>
> Is there a book or article that describes how to approach problems
> from a functional mindset?
>
> How did you "flip the switch" in your brain to the functional mindset?

I don't know whether there is a book, but I can tell you how I did it.
Just like you and most others I came from an imperative background.
First of all, don't try too hard.  It can be very frustrating, when you
are a beginner.  There is nothing wrong with writing nonidiomatic code
at the beginning.

I will give you some basic rules you can follow to get fluent in
Haskell:

  * Understand the syntax

    It happens to a lot of newbies that they get overwhelmed and totally
    confused by the number of symbols, which they have never seen before
    in other languages.  Don't panic!  Most of these symbols are
    ordinary functions.  If you disregard those, you will have a handful
    of symbols left, likely even less than in other languages.  Most of
    those are just syntactic sugar for, again, regular functions and
    function applications.  Haskell is an incredibly simple language at
    its core.

  * Understand the basics of the type system

    Haskell's type system is very sophisticated and can take months or
    years to understand fully, especially when you start working with
    some of the type system extensions.  But this pays off!  Once you
    know how to read and write type signatures you will find that most
    functions together with their type signatures are fairly
    self-explanatory.  I constantly learn the interface of new libraries
    by just looking at the types.

    The type system will also improve the safety of your programs up to
    the point where you will experience a strange sensation:  Once your
    program passes the compiler, it usually works!

    Finally you will find that it is advantageous to write a type
    signature, before writing the corresponding definition.  For example
    for a function to add two integers using only increment (succ) and
    decrement (pred), first write its type signature:

        add :: Integer -> Integer -> Integer

    And only after that write its definition:

        add x 0 = x
        add x y = add (succ x) (pred y)

    Firstly this will prepare your mind for the implementation, because
    you know what structure the function has to have.  Secondly it will
    prevent a broad class of bugs.

  * Know your tools

    This is about the most important rule, because in Haskell you have
    an incredible amount of abstractions and design patterns, which you
    simply cannot have in most other languages.  The introduction of
    laziness alone gives you many new design patterns you probably have
    never seen before.

    Of course in the beginning you will use the tools you know from
    other languages, as far as applicable to Haskell.  But the more you
    work with it, the more you will learn the 'other' tools.  And once
    you learned them, other languages will really annoy you. ;)

  * Understand the language semantics

    Finally this last point will give you the in-depth understanding of
    what is going on under the hood.  It will help you understand the
    tools you are using.  You will learn what "non-strict" actually
    means, what the "bottom" value is, how to prevent stack/heap
    overflows, etc.

Now don't just search for tutorials or books.  Instead, write
applications!  Haskell can be learned best by writing actual code.  I
will give you a very interesting problem to begin with.

The n-th Mersenne number is 2^n - 1.  There are certain Mersenne
numbers, which are prime numbers.  For this kind of numbers there exists
a fast primality test, which is also used in the large distributed prime
number searches like GIMPS.  It's called the Lucas-Lehmer primality test
and involves generating an infinite sequence of numbers and picking a
certain element from it.

This task is not just a great opportunity to learn functional thinking,
but in particular Haskell thinking, because you would solve the problem
differently in other functional languages.

In an imperative approach you would write a loop, which destructively
updates a variable a certain number of times, before reading its value.
The first translation of this to Haskell is to write a recursive
function, which uses function parameters and recursion as a replacement
for destructively updated variables.  This is not really an improvement,
as you will write essentially the same code, but with recursive calls
instead of destructive updates.  You got rid of the side effects, but
not of the general imperative idea of the computation.

Now comes the most important third point:  Know your tools!  In this
case you have a tool, which you won't find in most other languages:
infinite data structures, in particular infinite lists.  Using the
'iterate' combinator you can make a direct translation of this infinite
sequence.  You write an infinite list.  Then using the (!!) function you
just pick the element you want.  This has two advantages:  Firstly the
code is a straightforward translation of the mathematical definition of
the algorithm.  Secondly and more importantly you have a separation of
concerns here:  You have the infinite list.  Independent of that you
have the function to pick an element from it.  Independent of both you
have an IO computation to display the result.  This makes your code very
composable.

With this solution you have also used a second design pattern, which you
won't find in the mainstream languages:  corecursion.  At some point you
will learn to use these tools and design patterns more consciously.
This is your road to mastering Haskell.


Greets,
Ertugrul


-- 
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://ertes.de/