[Haskell-beginners] Fundamentals of List Comprehension and Recursion

[Brent Yorgey]

On Mon, Jan 02, 2012 at 09:07:35PM -0600, Cody Haberkorn wrote:
> Hi all,

Hi Cody, welcome!

> I high school programmer and just started learning Haskell. Haskell so far
> seems to be an awesome language. I began reading "Learn you Haskell for a
> Great Good!" I am confused with list comprehension, as I am coming from an
> imperative programming language (Java). From my understanding,
> list comprehension is synonymous to Java's for-loop and what not.

I can tell you are coming from an imperative background, because all
your explanations below are phrased in terms of what the code *does*.
Forget this way of thinking when learning Haskell!  Haskell code does
not *do* things; it *evaluates to* some value, in the same sense that
a mathematical expression like (3 + 4) * 6 evaluates ("simplifies") to
72.

> 
> For example:
> 
> let xs = [1,2,3,4,5]
> [x | x <- xs]
> 
> I believe it is saying that "bound x to xs, and do (print) x."

No, this code does not do anything, and it certainly does not print.
[x | x <- xs] evaluates to the list made up of the values 'x', where
'x' ranges over all the values in the list 'xs'.  That is, 
[x | x <- xs] is exactly equivalent to xs.

If you type this expression at the ghci command line, it will cause
the value of this list to be printed. But there is nothing inherent in
the above code to do with printing, just as there is nothing inherent
in the number '72' to do with pencil lead, although you may happen to
write down 72 using your pencil. (If you type 72 at the ghci prompt it
will also cause 72 to be printed: I hope you will agree that 72 does
not mean 'print 72', it just means 72!)

> Another example:
> 
> let rightTriangles' = [ (a,b,c) | c <- [1..10] , b <- [1.. c], a <- [1..
> b], a^2 + b^2 == c^2, a+b+c == 24]
> ghci > rightTriangles'
> [(6 ,8 ,10)]
> 
> I believe it is saying "store c with the numbers 1-10, b is length of c,
> and a is the length of b. Print the answer (a,b,c) which satisfies a^2 +
> b^2 == c^2, a+b+c == 24.

Again, there is no storing going on.  Also, b is not the length of c;
instead b will take on each of the numbers from 1 to c. This says 

  * let c refer to each of the numbers from 1 to 10 in turn
  * for each value of c, let b refer to each of the numbers from 1 to
    c in turn
  * for each value of b, let a refer to each of the numbers from 1 to
    b in turn
  * keep only those combinations where a^2 + b^2 == c^2 and a+b+c ==
    24
  * make a list out of triples (a,b,c) of the remaining combinations.

> -- Creating our own sum function
> sum ' :: (Num a) => [a] -> a

  This first line says: sum' is a function which works for any type a,
  as long as a is an instance of the Num type class (that is, it is a
  type which supports arithmetic operations, such as Integer or
  Double).  It takes a single input -- a list whose elements are of
  type a -- and produces a single output -- a value of type a.

  (By the way, you have put a space in between sum and the single quote
  ', but there should be no space, like sum' -- it is just a name;
  unlike Java, Haskell names allow single quotes as long as they are
  not at the beginning.)

> sum ' [] = 0

  If the input to sum' is the empty list, the output of sum' is 0.

> sum ' (x:xs) = x + sum ' xs

  If the input to sum' is a list whose first element is called x and
  whose remainder is called xs, the output of sum' is x plus the
  result of a recursive call to sum' with the input xs.

> Summed up: How did you learn Haskell and how long did it take before you
> became competent? This is my second day and I am already running into
> problems. I have to re-read things where as Java it came easy to me. Any
> book or tutorials? Can someone explain list comprehension and my recursion
> code?

It took me many months to learn Haskell.  I don't remember exactly how
I learned it, but it was a combination of reading tutorials, reading
and trying to understand lots of other people's code, and working on
my own projects.  If you are only on your second day, don't despair!
Your confusion and problems are quite natural.  Keep pushing through
them (and keep asking questions) and you will learn a lot.  The best
things in life do not come easily.

-Brent