{"id":824,"date":"2009-11-13T15:47:35","date_gmt":"2009-11-13T15:47:35","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2009\/11\/13\/writing-basic-functions-in-haskell-edited-repost\/"},"modified":"2009-11-13T15:47:35","modified_gmt":"2009-11-13T15:47:35","slug":"writing-basic-functions-in-haskell-edited-repost","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2009\/11\/13\/writing-basic-functions-in-haskell-edited-repost\/","title":{"rendered":"Writing Basic Functions in Haskell (edited repost)"},"content":{"rendered":"

(This is a heavily edited repost of the first article in my original
\nHaskell tutorial.)<\/em><\/p>\n

(I’ve attempted o write this as a literate haskell program. What that
\nmeans is that if you just cut-and-paste the text of this post from your
\nbrowser into a file whose name ends with “.lhs”, you should be able to run it
\nthrough a Haskell compiler: only lines that start with “>” are treated as
\ncode. The nice thing about this is that this blog post is itself a
\ncompilable, loadable Haskell source file – so I’ve compiled and tested
\nall of the code in here in exactly this context.)<\/em><\/p>\n

<\/p>\n

Haskell is a functional programming language. At the simplest
\nlevel, what that means is that you write programs by writing functions – and the
\nfunctions are truly mathematical functions: they take a set of inputs, and generate
\na set of outputs, and the result of the function call is dependent solely
\non the values of the inputs. So, the best way to start out
\nlooking at Haskell is to look at how to write basic functions.<\/p>\n

So let’s dive right in a take a look at a very simple Haskell definition
\nof the factorial function:<\/p>\n

\n> simplest_fact n = if n == 0\n>     then 1\n>     else n * simplest_fact (n - 1)\n<\/pre>\n
 This is the classic implementation of the factorial. Some things to
\nnotice:<\/p>\n
    \n
  1.  In Haskell, a function definition uses no keywords. Just “name
    \nparams = impl<\/code>“<\/li>\n
  2.  Function application is written by putting
    \nthings side by side. So to apply the factorial function to x<\/code>, we
    \njust write simplest_fact x<\/code>. Parens are only used for managing precedence.
    \nThe parens in “fsimplest_act (n - 1)<\/code>” aren’t there because the function
    \nparameters need to be wrapped in parens, but because otherwise, the default
    \nprecedence rules would parse it as “(simplest_fact n) - 1<\/code>“.<\/li>\n
  3.  Haskell uses infix
    \nsyntax for most mathematical operations. That doesn’t mean that they’re
    \nspecial: they’re just an alternative way of writing a binary function
    \ninvocation. You can define your own mathematical operators using normal
    \nfuncion definitions.<\/li>\n
  4.  There are no explicit grouping constructs in Haskell:
    \nno “{\/}”, no “begin\/end”. Haskell’s formal syntax uses braces, but the
    \nlanguage defines how to translate indentation changes into braces; in
    \npractice, just indenting the code takes care of grouping.\n<\/li>\n<\/ol>\n
     That implementation of factorial, while correct, is not how most Haskell
    \nprogrammers would normally implement it. Haskell includes a feature called
    \npattern matching<\/em>, and most programmers would use pattern matching
    \nrather than the if\/then<\/code> statement for a case like that. Pattern matching
    \nseparates things and often makes them easier to read. The basic idea of
    \npattern matching in function definitions is that you can write what look
    \nlike<\/em> multiple versions of the function, each of which uses a different set of
    \npatterns 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
    \nsomething like a conditional statement, but they’re completely separated at
    \nthe definition level. The case that matches the values at the point of call is
    \nthe one that is actually invoked. So here’s a more stylistically correct
    \nversion of the factorial:<\/p>\n
    \n> pattern_fact 0 = 1\n> pattern_fact n = n * pattern_fact (n - 1)\n>\n<\/pre>\n
     In the semantics of Haskell, those two are completely equivalent. In fact,
    \nthe deep semantics of Haskell are based on pattern matching – so it’s more
    \ncorrect to say that the if\/then\/else version is translated into the pattern
    \nmatching version than vice-versa! At a low level, both will basically be
    \nexpanded to the Haskell pattern-matching primitive called the
    \n“case<\/code>” statement, which selects from among a list of patterns:\n<\/p>\n
    \n> cfact n = case n of\n>              0 -> 1\n>              _ -> n * cfact (n - 1)\n<\/pre>\n
     Another way of writing the same thing is to use Haskell’s list type. Lists
    \nare a very fundamental type in Haskell. They’re similar to lists in Lisp,
    \nexcept that all of the elements of a list must have the same type. A list is
    \nwritten between square brackets, with the values in the list written inside,
    \nseparated by commas, like:<\/p>\n
    \n[1, 2, 3, 4, 5]\n<\/pre>\n
     As in lisp, the list is actually formed from pairs, where the first
    \nelement of the pair is a value in the list, and the second value is the rest
    \nof the list. Pairs are constructed<\/em> in Haskell using “:<\/code>“,
    \nso the list could also be written in the following ways:<\/p>\n
    \n1 : [2, 3, 4, 5]\n1 : 2 : [3, 4, 5]\n1 : 2 : 3 : 4 : 5 : []\n<\/pre>\n
     If you want a list of integers in a specific range, there’s a shorthand
    \nfor it using “..<\/code>“. To generate the list of values from
    \nx<\/code> to y<\/code>, you can write:<\/p>\n
    \n[ x .. y ]\n<\/pre>\n
     Getting back to our factorial function, the factorial of a number “n” is
    \nthe product of all of the integers from 1 to n. So another way of saying that
    \nis that the factorial is the result of taking the list of all integers from 1
    \nto n, and multiplying them together:<\/p>\n
    \nlistfact n = listProduct [1 .. n]\n<\/pre>\n
     But that doesn’t work, because we haven’t defined listProduct<\/code>
    \nyet. Fortunately, Haskell provides a ton of useful list functions. One of the
    \nuseful types of list operations is fold<\/em>, which comes in two versions:
    \nfoldl<\/code> and foldr<\/code>. What folds do is iterate over a
    \nlist using some functions to combine elements. It takes a function to merge
    \ntwo values, and an initial value for the merge. Then it takes the first
    \nelement in the list, and merges it with the initial value of the result. Then
    \nit takes the second value, and merges it with the result of the first. And so
    \non.<\/p>\n
     The difference between foldl<\/code> and foldr<\/code>
    \nis the associative order in which they do things: foldl<\/code> starts
    \nfrom the left, and foldr starts from the right.<\/p>\n
     To illustrate, suppose we had a list [1, 2, 3, 4, 5, 6]<\/code>. If
    \nwe did foldl (*) 1 [1, 2, 3, 4, 5, 6]<\/code>, it would evaluate as
    \n“(((((1 * 1) * 2) * 3) * 4) * 5) * 6”. That is, it would start with 1, and
    \nthen 2, and then 3, and so on. foldr<\/code> would group
    \nright-associative; it would do “1*(2*(3*(4*(5*(6*1)))))”. Since *<\/code>
    \nis associative, the result value doesn’t matter. But it can make a significant
    \ndifference in performance; the way that the Haskell ends up evaluating
    \nfunction calls, you can easily wind up with programs where foldr<\/code>
    \ncan be much faster that foldl<\/code>.<\/p>\n
     So, using fold, you can write the factorial using lists:<\/p>\n
    \n> listfact n = listProduct [ 1 .. n ]\n>        where listProduct lst = foldl (*) 1 lst\n<\/pre>\n
     One thing that some Haskell programmers like to do is to write
    \nwhat they call points-free<\/em> functions: that is, functions
    \nthat do not need to name any of their parameters. You can do an amazing
    \namount of stuff in points-free Haskell. Personally, I’m not a fan of
    \npoints-free programming: I find it much harder to read. But some people
    \nlove it.<\/p>\n
     To go points-free, you define a function in terms
    \nof series of compositions of other functions. The elements of
    \nthose compositions take care of pushing the values around to
    \nget them to the right place. For factorial, it’s pretty easy. There’s
    \na function called “enumFromTo<\/code>“, which takes two
    \nparameters, m and n, and generates a list of the values from m to n. Through
    \na haskell feature called currying, if you take a two-parameter
    \nfunction and only give it one parameter, you get back a one-parameter
    \nfunction. So:<\/p>\n
    \n> enumFromOne = enumFromTo 1\n<\/pre>\n
     is exactly the same as:<\/p>\n
    \nenumFromOne n = enumFromTo 1 n\n<\/pre>\n
     There’s a list function, “product<\/code>” which takes the product of
    \nall of the elements of a list – it’s basically a shorthand for “zipwith
    \n(*) 1<\/code>“. Finally, if you’ve got two functions f and g, you can
    \nwrite the composition of the two functions as g . f<\/code>. So,
    \nto write a points-free factorial function, you could just write:<\/p>\n
    \n> pointsfree_fact = product . (enumFromTo 1)\n<\/pre>\n
     I need to explain one more list function before moving on. There’s a
    \nfunction called “zipWith<\/code>>” for performing an operation pairwise
    \non two lists. For example, given the lists “[1,2,3,4,5]<\/code>” and
    \n“[2,4,6,8,10]<\/code>“, “zipWith (+) [1,2,3,4,5]
    \n[2,4,6,8,10]<\/code>” would result in “[3,6,9,12,15]<\/code>“.<\/p>\n
     Now we’re going to jump into something that’s going to seem really
    \nstrange. One of the fundamental properties of how Haskell runs a program is
    \nthat Haskell is a lazy<\/em> language. What that means is that no
    \nexpression is actually evaluated until its value is needed<\/em>. So you
    \ncan do things like create infinite<\/em> lists – since no part of the list is
    \ncomputed until it’s needed, you can create something that defines an infinite
    \nlist – but since you’ll never access more than a finite number of elements of
    \nit, it’s no problem. Using that, we can do some really clever things, like
    \ndefine the complete series of fibonnaci numbers:<\/p>\n
    \n> fiblist = 0 : 1 : (zipWith (+) fiblist (tail fiblist))\n<\/pre>\n
    This looks very strange if you’re not used to it. But if we tease it apart a
    \nbit, it’s really pretty simple:<\/p>\n
      \n
    1.  The first element of the fibonacci series is “0”.<\/li>\n
    2.  The second element of the fibonacci series is “1”.<\/li>\n
    3.  For the rest of the series, take the full fibonacci list, and
      \nline up the two copies of it, offset by one (the full list, and the
      \nlist without the first element), and add the values pairwise. <\/li>\n<\/ol>\n
       That third step is the tricky one. It relies on the laziness of Haskell:
      \nHaskell won’t compute the nth<\/em> element of the list until you
      \nexplicitly<\/em> reference it; until then, it just keeps around the
      \nunevaluated<\/em> code for computing the part of the list you haven’t
      \nlooked at. So when you try to look at the n<\/em>th value, it will compute
      \nthe list only up to<\/em> the n<\/em>th value. So the actual computed
      \npart of the list is always finite – but you can act as if it wasn’t. You can
      \ntreat that list as if<\/em> it really were infinite – and retrieve any
      \nvalue from it that you want. Once it’s been referenced, then the list up to
      \nwhere you looked is concrete – the computations won’t<\/em> be repeated.
      \nBut the last tail of the list will always be an unevaluated expression that
      \ngenerates the next<\/em> pair of the list – and that<\/em> pair will
      \nalways be the next element of the list, and an evaluated expression for the
      \npair after it.<\/p>\n
       Just to make sure that the way that “zipWith<\/code>” is working in
      \n“fiblist<\/code>” is clear, let’s look at a prefix of the parameters to
      \nzipWith<\/code>, and the result. (Remember that those three are all actually the
      \nsame list! The diagonals from bottom left moving up and right are the same
      \nlist elements.)<\/p>\n
      \nfiblist      = [0  1  1  2  3  5  8 ...]\ntail fiblist = [1  1  2  3  5  8  ...  ]\nzipWith (+)  = [1  2  3  5  8  13 ...  ]\n<\/pre>\n
      Given that list, we can find the n<\/em>th element of the list very
      \neasily; the n<\/em>th element of a list l<\/em> can be retrieved with
      \n“l !! n<\/code>“, so, the fibonacci function to get the n<\/em>th
      \nfibonacci number would be:<\/p>\n
      \n> list_fib n = fiblist !! n\n<\/pre>\n
       And using a very similar trick, we can do factorials the same way:<\/p>\n
      \n> factlist = 1 : (zipWith (*) [1..] factlist)\n> factl n = factlist !! n\n<\/pre>\n
       The nice thing about doing factorial this way is that the values of all of
      \nthe factorials less than<\/em> n are also computed and remembered, so the
      \nnext time you take a factorial, you don’t need to repeat those
      \nmultiplications.<\/p>\n","protected":false},"excerpt":{"rendered":"
      (This is a heavily edited repost of the first article in my original Haskell tutorial.) (I’ve attempted o write this as a literate haskell program. What that means is that if you just cut-and-paste the text of this post from your browser into a file whose name ends with “.lhs”, you should be able to […]<\/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-824","post","type-post","status-publish","format-standard","hentry","category-haskell"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-di","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/824","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=824"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/824\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=824"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=824"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=824"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}