I wasn’t really sure of quite how to start this off. I finally decided to just dive right in with a simple function definition, and then give you a bit of a tour of how Haskell works by showing the different ways of implementing it.<\/p>\n
I wasn’t really sure of quite how to start this off. I finally decided to just dive right in with a simple function definition, and then give you a bit of a tour of how Haskell works by showing the different ways of implementing it.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[89],"tags":[],"class_list":["post-228","post","type-post","status-publish","format-standard","hentry","category-haskell"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-3G","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/228","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=228"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/228\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=228"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=228"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=228"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nSo let’s dive right in a take a look at a very simple Haskell definition of the factorial function:
\nfact n = if n == 0
\nthen 1
\nelse n * fact (n – 1)
\nThis is the classic implementation of the factorial. Some things to notice:
\n1. In Haskell, a function definition uses no keywords. Just “`name params = impl`”.
\n2. Function application is written by putting things side by side. So to apply
\nthe factorial function to `x`, we just write `fact x`. Parens are only used for
\nmanaging precedence. The parens in “`fact (n – 1)`” aren’t there because the
\nfunction parameters need to be wrapped in parens, but because otherwise,
\nthe default precedence rules would parse it as “`(fact n) – 1`”.
\n3. Haskell uses infix syntax for most mathematical operations. That doesn’t mean that
\nthey’re special: they’re just an alternative way of writing a binary function
\ninvocation. You can define your own mathematical operators using normal function
\ndefinitions.
\n4. There are no explicit grouping constructs in Haskell: no “{\/}”, no “begin\/end”. Haskell’s
\nformal syntax uses braces, but the language defines how to translate indentation changes
\ninto braces; in practice, just indenting the code takes care of grouping.
\nThat implementation of factorial, while correct, is not how most Haskell programmers would implement
\nit. Haskell includes a feature called pattern matching<\/em>, and most programmers would use
\npattern matching rather than the `if\/then` statement for a case like that. Pattern matching separates
\nthings and often makes them easier to read. The basic idea of pattern matching in function
\ndefinitions is that you can write what *look like* multiple versions of the function, each of which
\nuses a different set of patterns for its parameters (we’ll talk more about what patterns look like in
\ndetail in a later post); the different cases are separated not just by something like a conditional statement, but they’re completely separated at the definition level. The case that matches the values at the point of call is the one that is actually invoked. So here’s a more stylistically correct version of the factorial:
\nfact 0 = 1
\nfact n = n * fact (n – 1)
\nIn the semantics of Haskell, those two are completely equivalent. In fact, the deep semantics of Haskell are based on pattern matching – so it’s more correct to say that the if\/then\/else version
\nis translated into the pattern matching version than vice-versa! In fact, both will basically expand to the Haskell pattern-matching primitive called the “`case`” statement, which selects from
\namong a list of patterns: *(Note: I originally screwed up the following, by putting a single “=” instead of a “==” inside the comparison. Stupid error, and since this was only written to explain things, I didn’t actually run it. Thanks to pseudonym for pointing out the error.)*
\nfact n = case (n==0) of
\nTrue -> 1
\nFalse -> n * fact (n – 1)
\nAnother way of writing the same thing is to use Haskell’s list type. Lists are a very fundamental type in Haskell. They’re similar to lists in Lisp, except that all of the elements of a list must have the same type. A list is written between square brackets, with the values in the list written
\ninside, separated by commas, like:
\n[1, 2, 3, 4, 5]
\nAs in lisp, the list is actually formed from pairs, where the first element of the pair is
\na value in the list, and the second value is the rest of the list. Pairs are *constructed* in Haskell using “`:`”, so the list could also be written in the following ways:
\n1 : [2, 3, 4, 5]
\n1 : 2 : [3, 4, 5]
\n1 : 2 : 3 : 4 : 5 : []
\nIf you want a list of integers in a specific range, there’s a shorthand for it using “`..`”. To generate the list of values from `x` to `y`, you can write:
\n[ x .. y ]
\nGetting back to our factorial function, the factorial of a number “n” is the product of all of the
\nintegers from 1 to n. So another way of saying that is that the factorial is the result of taking the list of all integers from 1 to n, and multiplying them together:
\nlistfact n = listProduct [1 .. n]
\nBut that doesn’t work, because we haven’t defined `listProduct` yet. Fortunately, Haskell provides
\na ton of useful list functions. One of them, “`foldl`”, takes a function *f*, an initial value *i*,
\nand a list *[l1<\/sub>, l2<\/sub>,…,ln<\/sub>]*, and basically does *f(ln<\/sub>(…f(l2<\/sub>, f(i,l1<\/sub>))))*. So we can use `foldl` with the multiply
\nfunction to multiply the elements of the list together. The only problem is that multiplication is written as an infix operator, not a function. In Haskell, the solution to *that* is simple: an infix operator is just fancy syntax for a function call; to get the function, you just put the operator
\ninto parens. So the multiplication *function* is written “`(*)`”. So let’s add a definition of `listProduct` using that; we’ll do it using a *`where`* clause, which allows us to define
\nvariables or functions that are local to the scope of the enclosing function definition:
\nlistfact n = listProduct [ 1 .. n ]
\nwhere listProduct lst = foldl (*) 1 lst
\nI need to explain one more list function before moving on. There’s a function called “`zipWith`” for performing an operation pairwise on two lists. For example, given the lists “`[1,2,3,4,5]`” and “`[2,4,6,8,10]`”, “`zipWith (+) [1,2,3,4,5] [2,4,6,8,10]`” would result in “`[3,6,9,12,15]`”.
\nNow we’re going to jump into something that’s going to seem really strange. One of the fundamental
\nproperties of how Haskell runs a program is that Haskell is a *lazy* language. What that means is
\nthat no expression is actually evaluated until its value is *needed*. So you can do things like
\ncreate *infinite* lists – since no part of the list is computed until it’s needed. So we can do
\nthings like define the fibonacci series – the *complete* fibonacci series, using:
\nfiblist = 0 : 1 : (zipWith (+) fiblist (tail fiblist))
\nThis looks incredibly strange. But if we tease it apart a bit, it’s really pretty simple:
\n1. The first element of the fibonacci series is “0”
\n2. The second element of the fibonacci series is “1”
\n3. For the rest of the series, take the full fibonacci list, and line up the two copies
\nof it, offset by one (the full list, and the list without the first element), and add the
\nvalues pairwise.
\nThat third step is the tricky one. It relies on the *laziness* of Haskell:
\nHaskell won’t compute the *nth* element of the list until you *explicitly*
\nreference it; until then, it just keeps around the *unevaluated* code for computing the part of the list you haven’t looked at. So when you try to look at the *n*th value, it will compute the list *only up to* the *n*th value. So the actual computed part of the list is always finite – but you can act as if it wasn’t. You can treat that list *as if* it really were infinite – and retrieve any value from it that you want. Once it’s been referenced, then the list up to where you looked is concrete – the computations *won’t* be repeated. But the last tail of the list will always be an
\nunevaluated expression that generates the *next* pair of the list – and *that* pair will always be the next element of the list, and an evaluated expression for the pair after it.
\nJust to make sure that the way that “`zipWith`” is working in “`fiblist`” is clear, let’s look
\nat a prefix of the parameters to `zipWith`, and the result. (Remember that those three are all
\nactually the same list! The diagonals from bottom left moving up and right are the same list elements.)
\nfiblist = [0 1 1 2 3 5 8 …]
\ntail fiblist = [1 1 2 3 5 8 … ]
\nzipWith (+) = [1 2 3 5 8 13 … ]
\nGiven that list, we can find the *n*th element of the list very easily; the *n*th element of a list *l* can be retrieved with “`l !! n`”, so, the fibonacci function to get the *n*th fibonacci
\nnumber would be:
\nfib n = fiblist !! n
\nAnd using a very similar trick, we can do factorials the same way:
\nfactlist = 1 : (zipWith (*) [1..] factlist)
\nfactl n = factlist !! n
\nThe nice thing about doing factorial this way is that the values of all of the factorials *less than* *n* are also computed and remember – so the next time you take a factorial, you don’t need to
\nrepeat those multiplications.<\/p>\n","protected":false},"excerpt":{"rendered":"