-------------------------[ Readings ]------------------------- We'll use "Real World Haskell", by Bryan O'Sullivan, Don Stewart, and John Goerzen, http://book.realworldhaskell.org/read/ . Read Chapters 1--2. You can peek ahead in Chapter 3. There is also "Learn You a Haskell for Great Good!" by Miran Lipovaca, http://learnyouahaskell.com/chapters . You may find its style more entertaining. ===================[ Getting used to Haskell's syntax ]=================== Haskell is the language where leading edge ideas are implemented and tested (as Scheme has been at the time when lexical bindings, first-class closures, and continuations were the leading edge). Unlike Scheme's and LISP's minimalistic approach to syntax, Haskell has a lot of syntax complexity. I feel that some of that complexity gets in the way of understanding which constructs are core and which are "syntactic sugar" and what they expand to. So it's important to spend some time with the GHCI shell (or Hugs) getting used to it. Be warned that the older Hugs and the newer and actively developed GHC support different syntaxes, and what works in one may not work in the other if deprecated or added in the meantime. Your initial experience with Haskell will be full of syntax errors. In Haskell, both function calls and creating lambdas by specifying some (but not all) arguments of a function need no special syntax: two tokens separated by a space may _already_ mean a function application, full or partial! So you may mean to do one thing, like write a pattern, but your actual expression does another, such as applies a function instead. In that case, you will likely get a confusing type error. You'll get the hang of it, and you'll get to like this syntax, but it needs practice. Here are a couple of links on understanding Haskell error messages: http://stackoverflow.com/questions/10375532/haskell-understanding-no-instance-for-error-messages-in-ghci http://ics.p.lodz.pl/~stolarek/_media/pl:research:stolarek_understanding_basic_haskell_error_messages.pdf Here are some notes on Haskell's syntax and the concepts behind it. ------------------------------------------------------------------------ 1. Lists: constructors and pattern matching are core; the rest is sugar. ------------------------------------------------------------------------ Read through Chapters 1--3 of Real World Haskell (http://book.realworldhaskell.org/read/) to get the hang of the basic list syntax. The most important thing to understand is that lists can only be constructed with the constructors : and [], and can only be operated on via pattern-matching these constructors. All other ways of describing lists (like [1,2,3,4] or "abcdefgh") reduce to these constructors (see https://www.haskell.org/onlinereport/exps.html#lists) and all functions that operate on lists must start with patter-matching on : and [] (read, e.g., the list functions in Prelude: look for the sources of tail, head, last, null, etc. in the https://www.haskell.org/onlinereport/standard-prelude.html, then look at ++ , map, and filter.) Just like LISP (and unlike Ruby or Java), lists are entirely transparent; unlike LISP, where writing a function to operate on a list you need to write the calls to the CAR and the CDR, in Haskell you only need to write the pattern to bind some variables to the head and the tail of a cons---and this "deconstruction" by pattern is really the only way to get them (of course, you can call functions like head and tail, but they just wrap these patterns, trivially). This is true for _all_ data types in Haskell: you can only build them with constructors, and you can only pick them apart for processing with pattern matching. There are no opaque special ways or structure hidden in "objects" that only "methods" can manage. The constructors : and [] are internal, but we can define our own list type that is isomorphic to the built-in. See List example below. --------------- 2. Parentheses. --------------- In C/C++, Java, and many other languages () is an operator that calls a function (and gets compiled down to "call" or "call*" instruction, ultimately). In LISP, parens are the main and only element of syntax. In Haskell, they are nothing of either kind, and are used only for affecting the order of operations or to group elements of a pattern---or not at all, when that order works out without them, or when $ is used: f $ g $ h x is f (g (h x)) (see https://hackage.haskell.org/package/base-4.8.0.0/docs/Data-Function.html) Note that without the parens f g h x is ((f g) h) x ! That's function f getting g as an argument and producing another function that gets h as an argument, and makes another function that finally is called on x. Intuitive this is not, and getting used to reading it requires time, but that time is a good investment. Function application ("calling a function") only needs the space between the function name and the argument. Work out what value answer computes, then run it, then understand why: answer = twice twice twice suc 0 twice f x = f (f x) suc x = x + 1 Note that the ()s above are the only ones actually needed. Hint: work out what a single application of twice does to a function. [[This example is from "An Overview of Miranda" by David Turner, https://www.cs.kent.ac.uk/people/staff/dat/miranda/overview.pdf; Miranda, a non-free language, was supplanted by Haskell, which built on it. Read the above paper for its history value, though, and for succinct explanations of the concepts that became the core of Haskell. Miranda has some patterns and operators that later Haskell abandoned. See prev.hs and note that '--' is Haskell's comment, not an operator as it is in Miranda! Suggestion: rewrite this code in Haskell so that it works.]] Since Haskell's function application is the most basic syntactic thing (it's hard to be more basic that a space between two tokens!), it's easy to mistakenly write a function application when you don't mean it. The resulting expression will likely not typecheck. For example, in the following parens are needed: head (x:xs) = x Without them, 'head x : xs' would look like an application of head to x, the result for some reason being :-ed with xs. This is not the list-matching pattern we were looking for! ---------------------------- 3. Prefix vs infix functions ---------------------------- Languages like C/C++ and Java distinguish between operators and functions (even though C++ allows one to define the meaning of an operator like '<<' with a function 'operator<<(..)'). In Haskell, you only have functions, but some of these functions support "infix" syntax. For example, + as in 2+3 is a function referred to as (+), and can be used as such: firefly:hs user$ ghci GHCi, version 7.8.3: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. Prelude> (+) 2 3 5 Prelude> :i (+) class Num a where (+) :: a -> a -> a ... -- Defined in ‘GHC.Num’ infixl 6 + The last line specifies + as an infix operator, associating to the left, with precedence 6. The left association means that 1+2+3+4 is actually ((1+2)+3)+4 By contrast, right association of (:) means that 1:2:3:4:[] is 1:(2:(3:(4:[]))), which, of course, is the only way a list can be constructed (see #1 above). Prelude> :i (:) data [] a = ... | a : [a] -- Defined in ‘GHC.Types’ infixr 5 : in Hugs, we see the same, but with slightly different syntax: Hugs> :i ++ infixr 5 ++ (++) :: [a] -> [a] -> [a] Hugs> :i : infixr 5 : (:) :: a -> [a] -> [a] -- data constructor Now notice that 1+2:3:[] means [3,3] not 1+(2:3:[]), which would produce a type error from trying to add a number to a list. This is because + binds stronger than : . The former has priority 6, the latter priority 5, and so + wins over : . For the relative precedence table of various common operators, see https://www.haskell.org/onlinereport/decls.html#fixity These priorities and associations (a.k.a. "fixity") define the form of the parsed Haskell sexp---i.e., which operation's node gets to be the parent and which one its child. Observe that 1:[] ++ 2:[] makes [1,2]. You'd think the order of operations would be (1:[]) ++ (2:[]) , but in fact the precedence of both : and ++ is 5, and both are right-associate, so it's actually 1 : ([] ++ (2:[])). Which works out to the same value [1,2]---check this! [I verified this with the ghc-dump-tree package that exposes the parsed Haskell sexps after syntactic desugaring and type-checking transformations. Look for the final ##Typechecked tree and be prepared to write tree simplifier for this sexp, as it includes many kinds of information besides the parse.] -------------------------------------------- 4. Functions of several arguments. Currying. -------------------------------------------- In Haskell, every function of two or more arguments is a higher-order function (this is almost a verbatim quote from the Miranda overview above). You can see this from the type notation that Haskell provides for its functions. For example, (+) is conventionally a function of two arguments. For example, 2+3 is (+) 2 3 is 5. But observe the type signature of (+): Prelude> :t (+) (+) :: Num a => a -> a -> a The "Num a =>" part is understandable: in order to be added, the values must be some kind of a numeric type, so the type variable "a" gets this additional constraint on it. But which part says "two arguments"? Compare this with a function that takes a number and returns a function that applies to a number and gets you a number: :t \ x -> ( \ y -> x + y ) \ x -> ( \ y -> x + y ) :: Num a => a -> a -> a There's no apparent difference in the type. Moreover, there's no difference in their operation: Prelude> (+) 2 3 5 is the same as: Prelude> ((+) 2) 3 5 Prelude> :t (+) 2 ((+) 2) :: Num a => a -> a Prelude> (\ x -> ( \ y -> x + y ) 2) 3 5 is the same as: Prelude> ( \ x -> ( \ y -> x + y )) 2 3 5 Prelude> :t \ x -> ( \ y -> x + y ) 2 (\ x -> ( \ y -> x + y ) 2) :: Num a => a -> a Indeed, the classic LISP lambda in which one argument of the two is fixed, (funcall ((lambda (x) (lambda (y) (+ x y))) 2) 3) => 5 would have the same type if LISP were typed. In LISP or Scheme, creating a function with a smaller number of arguments by closing over some arguments of a function with more arguments requires writing code as above, with explicit lambdas (or defuns). In contrast, for Haskell multi-argument functions, simply supplying some (but not all) arguments automatically creates a lambda in the remaining arguments! Just like with function calls via a mere space, the syntax of Haskell makes creating these lambdas very easy; sometimes, you may do so without realizing it. Moreover, these is no discernible difference between a function f that takes a parameter of type a and returns a function that maps another parameter of type b to whatever return type c, f :: a -> (b -> c) and a function f' that takes *two* arguments of types a and b and makes a c . In Haskell's notation, *both* are shown the same way: f' :: a -> b -> c Note that taking a function from type a to type b as an argument (i.e., taking an argument of the type a->b) is depicted differently: g :: (a->b) -> c For example: Prelude> :t map map :: (a -> b) -> [a] -> [b] Prelude> map show [1,2,3,4] ["1","2","3","4"] Prelude> map ( \ x -> x*x ) [1,2,3,4,5] [1,4,9,16,25] Prelude> map ( \ x -> (x, "foo") ) [1,2,3,4,5] [(1,"foo"),(2,"foo"),(3,"foo"),(4,"foo"),(5,"foo")] --varying different expressions that result in equivalent -- evaluations: Prelude> map ( \ x -> "foo" ++ show x ) [1,2,3,4,5] ["foo1","foo2","foo3","foo4","foo5"] Prelude> map ( \ x -> ((++) "foo" . show) x) [1,2,3,4,5] ["foo1","foo2","foo3","foo4","foo5"] Prelude> map ( \ x -> ((++) "foo") . show $ x) [1,2,3,4,5] ["foo1","foo2","foo3","foo4","foo5"] Prelude> map (\ x -> (++) "foo" (show x)) [1,2,3,4,5] ["foo1","foo2","foo3","foo4","foo5"] ------------------[ Transcript from class ]------------------ // I post my transcripts with all typos, so that you see // what the error messages look like. $ ghci GHCi, version 7.8.3: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. // Basic arithmetic has the infix syntax you expect. Prelude> 1+2 3 // Lists have a convenient shorthand Prelude> [1,2,3] [1,2,3] // ..but they really are built of cons cells, with ':' being the // infix operator that makes a cons cell Prelude> 1 : 2 : [] [1,2] Prelude> 1 : 2 : 3 : [] [1,2,3] // ..and this really means the following order of operations, Prelude> 1 : ( 2 : ( 3 : [])) [1,2,3] // ..this order arises from : being a infixr operator, i.e., // an infix operator that associates to the right: Prelude> :i : data [] a = ... | a : [a] -- Defined in ‘GHC.Types’ infixr 5 : data [] a = ... | a : [a] -- Defined in ‘GHC.Types’ infixr 5 : // If you want to use it as a function, you can, with this // syntax: Prelude> (:) 1 [] [1] // ..it's really all the same: Prelude> (:) 1 [] == 1 : [] True // In Haskell, lists can only contain one type of value. A list // cannot mix ints, chars, and whatever else (unlike LISP or Ruby); // it needs to be a "List of X" where all elements have type X. // So type inference sees integers and infers that all elements of // the list must be numeric. Think of "Num t" as a predicate // that must be true, the type Num t => [t] as "a list of any type, // so long as that type is a number". Prelude> :t [1,2,3] [1,2,3] :: Num t => [t] // ++ is append for any lists Prelude> [1,2,3] ++ [4] [1,2,3,4] Prelude> :i ++ (++) :: [a] -> [a] -> [a] -- Defined in ‘GHC.Base’ infixr 5 ++ // what's the type of append? Prelude> :t ++ :1:1: parse error on input ‘++’ // Oops, need to use the function syntax here. Prelude> :t (++) (++) :: [a] -> [a] -> [a] // Note that this type already poses some restrictions. // ++'s arguments must be lists of the same type of thing, // so mixing lists of ints and strings won't work: Prelude> [1,2,3] ++ ["foo", "bar"] :14:2: No instance for (Num [Char]) arising from the literal ‘1’ In the expression: 1 In the first argument of ‘(++)’, namely ‘[1, 2, 3]’ In the expression: [1, 2, 3] ++ ["foo", "bar"] // strings are really just lists of chars: Prelude> :t "bar" "bar" :: [Char] Prelude> :t ['a', 'b'] ['a', 'b'] :: [Char] Prelude> ['a', 'b'] == "ab" True Prelude> :i True data Bool = ... | True -- Defined in ‘GHC.Types’ // ..more type errors. Type inference algorithm sees // the Num requirement from 1 and Char requirement from 'c' // to the resulting type of the list, and cannot unify them: Prelude> [1, 'c'] :19:2: No instance for (Num Char) arising from the literal ‘1’ In the expression: 1 In the expression: [1, 'c'] In an equation for ‘it’: it = [1, 'c'] Prelude> 1 : 'c' : [] :20:1: No instance for (Num Char) arising from the literal ‘1’ In the first argument of ‘(:)’, namely ‘1’ In the expression: 1 : 'c' : [] In an equation for ‘it’: it = 1 : 'c' : [] // An empty list has type "list of some thing t", where t // is an abstract type variable, which gets no contraints Prelude> :t [] [] :: [t] // ..but when used with a number, it gets an extra constraint: Prelude> :t 1 : [] 1 : [] :: Num a => [a] // Type inference algorithm helpfully reports the subexpressions // it could not unify: Prelude> 1 : ( 'c' : []) :24:1: No instance for (Num Char) arising from the literal ‘1’ In the first argument of ‘(:)’, namely ‘1’ In the expression: 1 : ('c' : []) In an equation for ‘it’: it = 1 : ('c' : []) // Finite tuples of different types are allowed; it's just the // recursive, potentially endless lists aren't. Prelude> (1, 'c') (1,'c') Prelude> (1, 'c', [2,3]) (1,'c',[2,3]) // Note that the types of the 1st and 3rd tuple elements need not // be the same, they just need to be Num: Prelude> :t (1, 'c', [2,3]) (1, 'c', [2,3]) :: (Num t1, Num t) => (t, Char, [t1]) // Lambdas are easy. "\" reads "lambda" (imagine the downward stroke from the middle of \ to the lower left corner) Prelude> let f = \ x -> x // The only inference here is that whatever type comes in, the same comes out: Prelude> :t f f :: t -> t // But here, since x is added with 1, it must be Num: Prelude> let f = \ x -> x + 1 Prelude> :t f f :: Num a => a -> a // Num is a collection of operations, to which + belongs. // This is called a "typeclass", but what it means it that // if something admits + it's got to be a Num. You write // the particular definition for + on your type as an // "instance" of Num. More on this later. Prelude> :i Num class Num a where (+) :: a -> a -> a (*) :: a -> a -> a (-) :: a -> a -> a negate :: a -> a abs :: a -> a signum :: a -> a fromInteger :: Integer -> a -- Defined in ‘GHC.Num’ instance Num Integer -- Defined in ‘GHC.Num’ instance Num Int -- Defined in ‘GHC.Num’ instance Num Float -- Defined in ‘GHC.Float’ instance Num Double -- Defined in ‘GHC.Float’ // Partial application also creates lambdas, implicitly. // But one needs to mind the infix vs prefix syntax... Prelude> 1 + :33:4: parse error (possibly incorrect indentation or mismatched brackets) // This works: Prelude> (+) 1 :34:1: No instance for (Show (a0 -> a0)) arising from a use of ‘print’ In a stmt of an interactive GHCi command: print it // ..that was a warning, not an error! Haskell does not know how to print // a function so created. But it's there and has a type: Prelude> :t (+) 1 (+) 1 :: Num a => a -> a // ..and it's really the same as LISP's (lambda (x) (+ 1 x)): Prelude> let g = (+) 1 Prelude> :t g g :: Num a => a -> a Prelude> g 3 4 Prelude> g 6 7 // And it observes its type constraint: Prelude> g "foo" :40:1: No instance for (Num [Char]) arising from a use of ‘g’ In the expression: g "foo" In an equation for ‘it’: it = g "foo" // (:) 1 is a lambda, too! This partial application eats lists // (second argument of :) and makes lists: Prelude> :t (:) 1 (:) 1 :: Num a => [a] -> [a] Prelude> ((:) 1) [] [1] Prelude> ((:) 1) [2, 3] [1,2,3] // ..it's really the same as Prelude> let prep1 x = 1 : x Prelude> prep1 [2,3] [1,2,3] Prelude> :t prep1 prep1 :: Num a => [a] -> [a] // Let's write a recursive length function for lists, using pattern matching. // First test that we are not colliding with any existing function: Prelude> :i len Top level: Not in scope: ‘len’ Perhaps you meant ‘lex’ (imported from Prelude) // This multiline mode is convenient; otherwise, every new let with redefine our function; // but we need two patterns, one for the base case, one for the "inductive step". // But another common beginner syntax error awaits :) Prelude> :set +m Prelude> let len [] = 0 Prelude| len x:xs = 1 + len xs Prelude| :50:5: Parse error in pattern: len // The error is that the Haskell parser sees "len x" as application of len to x, // and then : , because application (over a space) has higher precedence! // We must enclose the pattern inside ()s: Prelude> let len [] = 0 Prelude| len (x:xs) = 1 + len xs Prelude| // This works, for all types! So we get both strict type enforcement // and the ability to write generic code. This is known as "parametric polymorphism" // and is a core idea of Haskell. Prelude> len [] 0 Prelude> len [1,3] 2 Prelude> len ["foo", "bar", "baz"] 3 Prelude> len "foofoo" 6 // Note how the type of the return value is inferred. There's a + there, // so Num is imposed on it. Prelude> :t len len :: Num a => [t] -> a // Let's write a recursive append (the built-in append is ++). Prelude> :i app Top level: Not in scope: ‘app’ // Append is really easy with patterns! Prelude> let app [] x = x Prelude| app (x:xs) y = x : app xs y Prelude| Prelude> app [] [1,3,5] [1,3,5] Prelude> app [2,3] [1,3,5] [2,3,1,3,5] Prelude> app "foo" "bar" "foobar" // It works and enforces the type restriction that both arguments // must be lists of the same type of thing. Under the hood, // inference starts with two different type variables, then // unifies them when it sees [a] and [b] being used with :, // and only a remains Prelude> :t app app :: [a] -> [a] -> [a] // Types strictly enforced. 1st argument infers [Char], 2nd infers [Num], // they fail to unify. Prelude> app "foo" [1,3] :68:12: No instance for (Num Char) arising from the literal ‘1’ In the expression: 1 In the second argument of ‘app’, namely ‘[1, 3]’ In the expression: app "foo" [1, 3] // Partial application makes lambdas, as before: Prelude> let f = app "foo" Prelude| Prelude> :t f f :: [Char] -> [Char] Prelude> f "string" "foostring"