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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
