Types are capitalized. Lower-case types in signatures are placeholders in polymorphic functions. The signature
(.) :: (b -> c) -> (a -> b) -> (a -> c)
means: The function that is the . takes a first argument (g) that maps some type b to some type c. The second argument (f) maps some type a to the type b. This ensures that you can always do g(f(x)). The result of the function . is a function that maps the type a (what f takes) to type c (what g returns).The type signature only deals with types; this is not connected to the names of the function parameters.
Lambda expressions are written without types; they can be inferred (i.e. the return type is not void* , but exactly determined by the compiler). A lambda expression in lambda calculus notation would be written "λx.(+ x 1)". Haskell slightly modifies this, and allows infix operators: "\x -> x + 1"(the \ looks a bit like λ). Punctuation functions are infix by default.
About the data expression: This constructs a new type (typedef). The "|" operator is just used in a declarative fashion. Every time you write Empty in your source code, that thing is a list. The expression "list = Cons foo Empty" would create a list of one element (foo). A cons cell is a pair, this terminology is popular in Lisp. These confusing data type constructors allow pattern matching, as you have seen in the definition of "map": If the list is Empty, return Empty. If the list is a Cons of an element and another list, then return a Cons of (result of our function applied to that element) and (the rest of the list mapped) – recursion.
> Would be great if you offered an example where the argument and return type differed. As is, I don't know which order the Haskell declaration uses.
In Haskell, the last (rightmost) type is the return type. eg. countLetters :: String -> Int means it takes an argument of type String and returns an argument of type Int. Also, types are chained together so for example, foobar :: String -> Int -> Bool is a function that takes two arguments, the first being a String, the second an Int and it returns a Bool and foobarbaz :: String -> Int -> Bool -> Char is a function that takes three arguments, the first a String, the second an Int, the third a Bool and it returns a Char. This syntax makes a lot of sense when exploiting "higher-order functions" and "currying". I mention this only to provide keywords for your personal search.
> If this is essential at this point, it should be fleshed out more. Otherwise it feels like a distracting aside and out of place in a short introduction.
In my view this is an aside.
> Not clear why the left side is (.). Is this because it's non-alpha? Because it's infix? Something else? Order to read right hand side still unclear. Also don't know if reuse of a, b, and c as variables is significant.
To write a function whose name starts with a punctuation character, Haskell syntax demands that it is wrapped by brackets and I think its automatically infix. You can use any function infix by wrapping it in ` eg. x `f` y is the same as f x y which means (f x) y which means apply the function f to the argument x, and then to the argument y.
'a', 'b' and 'c' are type variables, similar to type variables in Java and C# when dealing with generics. They can stand for any type. So, 'a' could be String or Char or Bool or any other type. As could 'b' and 'c'. So 'a' may or may not be the same type as 'b' or 'c'.
I'm not sure I can make it any clearer but note the signature of (.) has two arguments and a single return type. The first argument is (b -> c) which means it is a function that takes a single argument 'b' and returns a value of type 'c'. So the first argument of (.) is a function. The second argument is (a -> b) which is also a function. Its return type is also a function.
Personally I think (.) is a very hard function to grok and certainly far too complex for the first higher order function you see, exponentially so if you're still trying to understand Haskell syntax.
> Would help to define a "cons cell". Is Cons a data type or a function here? Is there a standard for capitalization? Not clear to me how the 'a' on the left side relates to the two on the right. Is 'data' a keyword, a type, or something else?
data is a keyword. Its how you define a data structure in Haskell. In this case, its defining a data structure called List which will wrap elements of type 'a'. In other words, 'List Int' is a type, 'List Bool' is a type, 'List Char' is a type. List is broadly the same as generic in Java or C# where List<String> is a type and List<Bool> is a different type. Cons is a data constructor (and yes, its standard to capitalise data contructors), which you can think of as being a function Cons :: a -> List a -> List a. It takes two arguments, an 'a' and a 'List a' and returns a 'List a'. Here the type variable 'a' does something as Haskell ensures that if the first argument is an Int, then the second must be a List Int and will return a List Int. If the first argument is a String however, then the second must be a List String and will return a List String.
> I think a gloss of what 'λe' actually means would help
λe means "create an anonymous function that takes an argument called e with any type". And (λe -> e + 1) is an anonymous function that adds one to every element passed to it.
Seriously, check out Learn You a Haskell.
Now, about your questions…
float foo(int);
translates to foo :: Int -> Float
Now there's still a slight difference: in C, the prototype can be used as a forward declaration. The Haskell equivalent is merely a type restriction. Here it says "dear compiler, whatever you may think about that 'foo' thing, I'm telling you this is a function from integers to floating points.Oh, and type names are capitalized in Haskell. "list" was a typo.
Now,
(.) :: (b -> c) -> (a -> b) -> (a -> c)
reads in a similar way. On the left side of '::', we have an identifier (which here happens to be an infix operator, hence the surrounding parentheses). On the right side of '::', we have the type we wish to declare (which here is a bit complicated). g . f = λx -> g (f x)
I'm just defining a new value here. The left side of '=' tells us we define the dot operator (which is a function with two arguments), and the right hand side is just the body of the function. λx -> blah_blah
is a functional value. 'λ' and '->' are the syntax constructs. 'x' is the parameter, and 'blah_blah is the body. This code reads "the function which produces 'blah_blah' from 'x'". I call this a "literal" function, or a functional literal, because it is analogous to integer literals 42
and string literals:"Hello World"
(Oh and in Haskell, we actually use '\', not 'λ'.)
A cons cell is just a place where you store two values. Here this particular cons cell contains an element, and a pointer to the rest of the list. I reckon I was going way too fast on that one.
In type declarations, the arrow is right associative. So,
foo :: a -> b -> c
is the same as foo :: a -> (b -> c)
You can think of it as a functions with two arguments, or as a function with one arguments, which returns a function with the remaining argument. map (a -> b) -> List a -> list b
Lacks the '::' because I forgot to write it. Good catch. Likewise 'dbl_all' is a typo, it should be 'square_all' or something.
I'm a C programmer, and I've gone through the article a couple times without enlightenment. This isn't necessarily the fault of the article, but thought I'd offer the places I couldn't follow. Perhaps they will be useful for understanding a beginners viewpoint.
Would be great if you offered an example where the argument and return type differed. As is, I don't know which order the Haskell declaration uses. If this is essential at this point, it should be fleshed out more. Otherwise it feels like a distracting aside and out of place in a short introduction. This seems perfectly clear, which makes me suspect the other parts are intended to be simple as well. Not clear why the left side is (.). Is this because it's non-alpha? Because it's infix? Something else? Order to read right hand side still unclear. Also don't know if reuse of a, b, and c as variables is significant. Can't quite follow, but this might be because I'm not sure if the λ is syntactically important, or just a naming convention. I can't figure out what this means, possibly because I'm not sure what 'literally' means in this context. Also wasn't clear at first that "1" was meant as a number (or is that an 'L'), not a footnote or reference. Would help to define a "cons cell". Is Cons a data type or a function here? Is there a standard for capitalization? Not clear to me how the 'a' on the left side relates to the two on the right. Is 'data' a keyword, a type, or something else? Throughout this whole section, I had no idea which characters were one's and which were L's. I ended up cutting and pasting into emacs and capitalizing. Perhaps something other than 'l' for the placeholder variable? Or it is more than a placeholder? The concept seemed straightforward, but the example was very hard to figure out. Would help to mention this before the (.) example. So I guess this means the argument is on the left of the first '->' and the return type is to the right? And how should '->' be pronounced when spoken? I'm guessing 'e' is 'element', and lower-case 'L' is list. Why/when did we switch from 'a' in the definition of List? And where did 'foo' come from? Is this a builtin function? A user defined function? Is the lower case for the last 'list' important? For that matter, is case important at all in Haskell? Also, are the types on the left for 'a' and 'b' defined by the given types on the right? Also haven't figured out why this declaration(?) has no '::' as the others do. Is that supposed be 'dbl-all' at the end? And should that be "2 * e" instead of "e * e"? I'm hoping these are typos, otherwise I'm understanding even less than I thought. Great! Confirmation on how to read the function declarations. Now back to reread the first half of the article again. Hopefully this means the return type is after the last '->'? Unfortunately, I still don't feel confident in my ability to decipher now that I have have the been given those fundamentals. I think a gloss of what 'λe' actually means would help. As a type, is it parallel to "void * (* e)( void * )" in C?Despite this long list, I appreciate that you wrote the article. Much better to have something possibly flawed than nothing at all. Maybe one day I'll actually understand it!