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. 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? By the way, what branch of discrete math - other than the obvious ones such as logic and set theory - does functional programming fall under? Many thanks in advance for your help Paul

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

Brandon S. Allbery KF8NH wrote:

On Feb 18, 2007, at 21:44 , Michael Vanier wrote:

...

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

Function application never applies to pattern matching.

You're right; I take it back. However, ":" is not an acceptable variable name as such either: ghci> let foo x : y = x <interactive>:1:4: Parse error in pattern ":" needs to be surrounded by parens to be treated as a function; otherwise it's an operator. OK, we can try: ghci> let foo x (:) y = x <interactive>:1:10: Constructor `:' should have 2 arguments, but has been given 0 In the pattern: : In the definition of `foo': foo x : y = x Bottom line: "foo x:y" is not a valid pattern.

...

The usual answer to this is "category theory" which is an extremely abstract branch of mathematics. But you

Actually, no; my understanding is that category theory as applied to Haskell is a retcon introduced when the notion of monads was imported from category theory, and the original theoretical foundation of Haskell came from a different branch of mathematics.

Nevertheless, a lot of Haskell papers do refer to category theory, and lambda calculus can be put into that framework as well, so I don't think my statement is invalid. But as you say, it's a bit of an after-the-fact realization. Mike

P. R. Stanley wrote:

What are the pre-requisites for Lambda calculus? Thanks Paul

Learning lambda calculus requires no prerequisites other than the ability to think clearly. However, don't think that you need to understand all about lambda calculus in order to learn Haskell. It's more like the other way around: by the time you've learned Haskell, you've already unwittingly absorbed a good deal of lambda calculus. Once again, I recommend Pierces _Types and Programming Languages_ as a reference if you really feel you need to learn this now. For absorbing the functional style of programming (which is what you really should be working on at this point), the book _Structure and Interpretation of Computer Programs_ by Abelson and Sussman (which uses Scheme, not Haskell) is very valuable. For learning about recursion, the book _The Little Schemer_ by Friedman and Felleisen is also very good (and quite short); it also uses Scheme. However, most of the insights of both books carry over into Haskell (with a change of syntax, of course). Mike

For absorbing the functional style of programming (which is what you really should be working on at this point),

For functional style and the reasoning attitude associated with lazy functional programming, the following book is a good introduction: @Book{Bird-2000, author = {Richard Bird}, title = {Introduction to Functional Programming using {Haskell}}, year = 2000, publisher = {Prentice-Hall} } This is the second edition of: @Book{Bird-Wadler-1988, year = 1988, title = {Introduction to Functional Programming}, publisher = {Prentice-Hall}, author = {Richard Bird and Phil Wadler} } Wolfram

P. R. Stanley wrote:

Chaps, is there another general pattern for mylen, head or tail? mylen [] = 0 mylen (x:xs) = 1 + mylen (xs)

head [] = error "what head?" head (x:xs) = x

tail [] = error "no tail" tail (x:xs)= xs

There are of course stylistic variations possible, e.g. you can use case instead of pattern bindings: mylen list = case list of [] -> 0 (x:xs) -> 1 + mylen (xs) As you see, this moves pattern matching from the lhs to the rhs of the equation. Another very common 'pattern' is to factor the recursion into a generic higher order function fold op z [] = z fold op z (x:xs) = x `op` (fold op z xs) -- parentheses not strictly necessary here, added for readability and define mylen in terms of fold mylen = fold (+) 0 You also have the possibility to use boolean guards as in mylen xs | null xs = 0 | otherwise = 1 + mylen (tail xs) (Although here we use the more primitive functions (null) and (tail) which in turn would have to be defined using pattern matching. Pattern matching is the only way to examine data of which nothing is known other than its definition.) Lastly, there are cases where you want to use nested patterns. For instance, to eliminate successive duplicates you could write elim_dups (x:x':xs) = if x == x' then xs' else x:xs' where xs' = elim_dups (x':xs) elim_dups xs = xs Here, the first clause matches any list with two or more elements; the pattern binds the first element to the variable (x), the second one to (x'), and the tail to (xs). The second clause matches everything else, i.e. empty and one-element lists and acts as identity on them.

This pattern matching reminds me of a module on formal spec I studied at college.

As long as your code doesn't (have to) use a tricky algorithm (typically if the algorithm is more or less determined by the data structure, as in the above examples) then it is really like an executable specification. Cheers Ben