[Haskell-cafe] Recursion in Haskell

[Michael Vanier]

P. R. Stanley wrote:
> Brandon, Chris, Don,
> gentlemen,
> Thank you all for your swift and well-written answers.
> I should point out that I'm coming to functional programming with a 
> strong background in programming in C and C-type languages. I am also 
> very new to the whole philosophy of functional programming. Hence my 
> bafflement at some of the very elementary attributes of Haskell. I 
> thought that would give you chaps a better idea of where I'm coming from 
> with my queries.
> Back to mylen. Here is the definition once more:
> mylen [] = 0
> mylen (x:y) = 1 + mylen y
> The base case, if that is the right terminology, stipulates that the 
> recursion ends with an empty list and returns 0. Simple though one 
> question - why does mylen require the parentheses even when it is 
> evaluating the length of [...]? I can understand the need for them when 
> dealing with x:... because of the list construction function precedence 
> but not with [2,3,etc]. I thought a [e] was treated as a distinct token.
> 
> I'm assuming that the interpreter/compiler is equipped to determine the 
> type and value of xs subsequent to which it calls itself and passes the 
> object minus the first element as argument unless the object is an empty 
> list.

I think what you're asking here is why you need the parens around (x:y) in the 
second case.  Function application doesn't use parentheses, but it has a very 
high precedence, so "mylen x:y" would be parsed as "(mylen x) : y", since the 
":" constructor has a lower precedence.

> 
> going back to Don's formal definition of the list data structure:
> data [a] = [] | a : [a]
> A list is either empty or contains an element of type a? Correct, wrong 
> or very wrong?

A list is either empty, or consists of the first object, which is of type a 
(just called "a" here) and the rest of the list, which is also a list of type a 
(called "[a]" here).  The syntax is an impediment to understanding here; a 
clearer version of the list type would be

data List a = Empty | Cons a (List a)

The left-hand case says that a list can be just Empty.  The right-hand case says 
that a list can also be a "Cons" of a value of type a (the first element) and a 
List of type a (the rest of the list).

So, for instance, in my definition these are all lists:

Empty
Cons 10 Empty  -- list of Int
Cons 10 (Cons 20 Empty)
Cons "foo" (Cons "bar" (Cons "baz" Empty))  -- list of String

Using normal Haskell lists these are:

[]
10 : Empty  -- also written as [10]
10 : 20 : Empty -- also written as [10, 20]
"foo" : "bar" : "baz" : Empty -- also written as ["foo", "bar", "baz"]

The list syntax e.g. [1, 2, 3] is just syntactic sugar; the "real" syntax would 
be with the : operator e.g. 1 : 2 : 3 : [].  We use the sugar because it's 
easier to read and write.

> 
> By the way, what branch of discrete math - other than the obvious ones 
> such as logic and set theory - does functional programming fall under?
> 

The usual answer to this is "category theory" which is an extremely abstract 
branch of mathematics.  But you don't really need to know category theory to 
program in Haskell (though it helps for reading Haskell papers).  Also, lambda 
calculus is useful, and there is a field called "type theory" which is also 
useful.  Pierce's book _Types and Programming Languages_ will get you up to 
speed on lambda calculus and type theory, though it doesn't use Haskell.

Mike