On Feb 18, 2007, at 21:26 , P. R. Stanley wrote:
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
Because it would expect three parameters without the parentheses. ":" is a perfectly valid variable name; the convention in Haskell is that such names represent infix functions, but this is only a convention. The ability to use such names is convenient when passing operators or functions as parameters (this is, after all, functional programming!). BTW, it might also help to understand how mylen is rewritten by the compiler: mylen xx = case xx of [] -> 0 (x:xs) -> 1 + mylen xs ("xx" being actually an internal identifier which will never conflict with any name you use)
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?
Either empty, or an "a" consed with (the ":" is pronounced "cons") a list of "a". This is a recursive definition. "a" is an unspecified type; the formal definition allows any number (including zero, via []) of values of the same unspecified type to be combined into a list recursively as a : a : a : ... : []. The [a,a,a...] syntax is a convenient alternative syntax for a:a:a:...:[]; the two forms are completely equivalent, but the cons syntax is more convenient for pattern matching a list as (head:tail). -- brandon s. allbery [linux,solaris,freebsd,perl] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH