[Haskell-cafe] Recursion in Haskell

[Brandon S. Allbery KF8NH]

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 at kf8nh.com
system administrator [openafs,heimdal,too many hats] allbery at ece.cmu.edu
electrical and computer engineering, carnegie mellon university    KF8NH