{"id":232,"date":"2006-12-03T20:11:53","date_gmt":"2006-12-03T20:11:53","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2006\/12\/03\/building-datatypes-in-haskell-part-1\/"},"modified":"2006-12-03T20:11:53","modified_gmt":"2006-12-03T20:11:53","slug":"building-datatypes-in-haskell-part-1","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2006\/12\/03\/building-datatypes-in-haskell-part-1\/","title":{"rendered":"Building Datatypes in Haskell (part 1)"},"content":{"rendered":"

For this post, I’m doing a bit of an experiment. Haskell includes a “literate” syntax mode. In literate mode, and text that doesn’t start with a “>” sign is considered a comment. So this entire post can be copied and used as a source file; just save it with a name ending in `”.lhs”`. If this doesn’t work properly, please post something in the comments to let me know. It’s more work for me to write the posts this way, so if it’s not working properly, I’d rather not waste the effort. I’ve tested it in both Hugs and ghci, and everything works, but who knows what will happen after a pass through MovableType!<\/em><\/p>\n

Like most modern programming languages, Haskell has excellent support for building user-defined data types. In fact, even though Haskell is very much not<\/em> object-oriented, most Haskell programs end up being centered around the design and implementation of data structures.<\/p>\n

So today, I’m going to start looking at how you implement data types in Haskell. What I’m
\ngoing to do is start by showing you how to implement a simple binary search tree. I’ll start with
\na very simple version, and then build on that.<\/p>\n

<\/p>\n

The most common form of user-defined data type in Haskell is a constructed<\/em> data type.
\nConstructed types are types with one or more variants<\/em>, each of which has an associated
\n*constructor function*. The names of constructor functions must be unique to the type. Let’s start
\nwith a very simple version of a binary search tree containing integers. We’ll build it so that there
\nare empty nodes and non-empty nodes. Every non-empty node of the tree has an integer value, a left
\nchild, and a right child. A declaration for that would look like the following:<\/p>\n

\n>data SimpleIntBST = SIBNode Integer SimpleIntBST SimpleIntBST\n>                  | SIBEmpty\n<\/pre>\n
What this says is: we’re defining a data type named SimpleIntBST<\/code>. There are two kinds of SimpleIntBST<\/code> values. The first kind is an SIBNode<\/code>, which contains an integer value, a left child, and a right child. The other kind is an SIBEmpty<\/code>, which contains no values. SIBNode<\/code> and SIBEmpty<\/code> are the names of the constructor functions<\/em> that are used to create values. To create an
\nSIBNode<\/code>, you call it like a normal function with parameters of the correct type: for example, to create an SIBNode<\/code> containing the value “4” with empty left and right children, you’d write:<\/p>\n
\nSIBNode 4 SIBEmpty SIBEmpty\n<\/pre>\n
 Let’s try that in GHCI:<\/p>\n
\n*Main> SIBEmpty\n<interactive>:1:0:\nNo instance for (Show SimpleIntBST)\narising from use of `print' at <interactive>:1:0-7\nPossible fix: add an instance declaration for (Show SimpleIntBST)\nIn the expression: print it\nIn a 'do' expression: print it\n<\/pre>\n
 What’s wrong? The interpreter tried to print out the value returned by the expression.
\nThe interpreter outputs values using the print<\/code> function. In general in Haskell, when we
\nhave a problem like this, we look at types. What’s the type of the print<\/code> function?<\/p>\n
\n*Main> :type print\nprint :: (Show a) => a -> IO ()\n*Main>\n<\/pre>\n
 The parameter to print<\/code> must be a value of some type that is an instance of the Show<\/code> class. But we didn’t make our binary tree an instance of Show<\/code>. Fortunately, since Show<\/code> is such a fundamental interface, Haskell provides a nifty shorthand to make the compiler *generate* the code necessary to provide an implementation of whatever is needed for Show<\/code>, called a *deriving* clause. Let’s try again, this time with a deriving clause. We’ll call the new version “IntBST” rather than “SimpleIntBST”, because treating
\nthis post as a literate file, we can’t re-declare “SimpleIntBST”.<\/p>\n
\n>data IntBST = IBNode Integer IntBST IntBST\n>                  | IBEmpty deriving (Show)\n<\/pre>\n
Now, loading that into GHC, we’ll see:<\/p>\n
\n*Main> IBNode 4 IBEmpty IBEmpty\nIBNode 4 IBEmpty IBEmpty\n*Main>\n<\/pre>\n
Which is exactly what we want: our binary search tree is now printable.<\/p>\n
A data structure like this isn’t useful without some operations to work with it. So let’s
\ngo ahead and do some implementing! We’ll start with an insert operator:<\/p>\n
\n>ibstInsert :: IntBST -> Integer -> IntBST\n>ibstInsert (IBNode i left right) v\n>        | i > v = IBNode i (ibstInsert left v) right\n>        | otherwise = IBNode i left (ibstInsert right v)\n>ibstInsert IBEmpty v = (IBNode v IBEmpty IBEmpty)\n<\/pre>\n
 So let’s look at that a bit. It starts off with an explicit type declaration. It’s not strictly
\nnecessary, but it’s a good practice to put it there. Then we get to the real definition, which is
\nwhere things get interesting. I’m sure you noticed that there was something a bit strange about the
\ntype declaration for IntBST<\/code>. In most non-functional languages, you define a new data type as some kind of a record<\/em> or structure<\/em>, which contains a list of named<\/em> fields; when you use the structure, you access its fields by derefencing an instance of the data structure using the name of a field. But in our Haskell binary search tree, the values belonging to an instance of the data structure don’t have names<\/em>. Like most functional languages, Haskell uses pattern matching<\/em> to access the pieces of a data structure. <\/p>\n
 A pattern<\/em> looks like a value expression, except that it may contain some unbound<\/em> variables. The pattern can also be followed by a guard expression<\/em> which
\nis a boolean expression using variables bound in the pattern. If the guard is included, it’s separated from the patterns by a |<\/code> character, which is generally read as “such that”.
\nSo the first declaration line of ibstInsert<\/code> has two patterns: (IBNode i left right)<\/code>, and v<\/code>. It’s followed by a guard. So that full declaration line can be read as “ibstInsert of an IntBST matching ‘(IBNode i left right)<\/code>‘ and a value matching ‘v<\/code>‘ such that<\/em> ‘i > v<\/code>‘ returns ‘(IBNode i left right)<\/code>‘.<\/p>\n
 As a shorthand, if you have a guard expression on an indented line following a pattern
\nwith a guard, the pattern is reused with the second guard. So the second line
\nstarting with a “|<\/code>” is used if the first guard fails. As a guard expression,
\n“otherwise<\/code>” can only be used as the last<\/em> guard for a pattern, and
\nit’s always true.<\/p>\n
 So the first case of the declaration of ibstInsert<\/code>, in full, does the
\nfollowing:<\/p>\n
    \n
  1.  If the tree parameter is an IBNode<\/code>, then bind “i” to the value
    \nelement of the node, “left” to the left subtree, and “right” to the right subtree; and
    \nbind the variable “v” to the second parameter, which is the value to be inserted to the tree.<\/p>\n
  2.  If the value in the tree node is larger than the value being inserted, then return a tree that’s the same as this, except that the value is inserted into the left<\/em> subtree.\n
  3.  Otherwise, return a tree like this one, except that the new value is inserted
    \ninto the right<\/em> subtree.\n<\/ol>\n
     The second case says that if the node is an empty, then return a new non-empty node with
    \nthe new value as its value, and with empty left and right children.<\/p>\n
     If you look at the code now that you know how to read it, one thing that should hopefully be rather striking about it is just how much it looks like the explanatory pseudo-code that you’d
    \nfind in an algorithms textbook. It’s very straightforward code, written in a very easy to read style. (As a brief aside, this is an example of one of the things that really attracts me to Haskell programming. Code in Haskell tends to very naturally decompose into very small definitions that
    \nlook and read like explanatory code from a textbook.)<\/p>\n
     So let’s look at a quick example of using this to build a tree.<\/p>\n
    \n>treeone = ibstInsert (ibstInsert (ibstInsert (ibstInsert (ibstInsert IBEmpty 3) 5) 2) 17) 10\n>treetwo = (ibstInsert (ibstInsert (ibstInsert (ibstInsert treeone 4) 6) 1) 9)\n<\/pre>\n
    That gives us two trees, one of which contains a subset of the values in the other. We can ask ghc to show us the values of them:<\/p>\n
    \n*Main> treeone\nIBNode 3 (IBNode 2 IBEmpty IBEmpty) (IBNode 5 IBEmpty (IBNode 17 (IBNode 10 IBEmpty IBEmpty) IBEmpty))\n*Main*gt; treetwo\nIBNode 3 (IBNode 2 (IBNode 1 IBEmpty IBEmpty) IBEmpty) (IBNode 5 (IBNode 4 IBEmpty IBEmpty) (IBNode 17 (IBNode 10 (IBNode 6 IBEmpty (IBNode 9 IBEmpty IBEmpty)) IBEmpty) IBEmpty))\n*Main>\n<\/pre>\n
     The other thing that we want to be able to do with a binary search tree is find nodes in it. Since our current BST only contains integers, we’ll just write a function that returns a boolean value indicating whether or not a particular value is in the tree.<\/p>\n
    \n>\n>ibstSearch :: IntBST -> Integer -> Bool\n>ibstSearch (IBNode k left right) v\n> \t    | k == v = True\n>        | k > v = ibstSearch left v\n>        | otherwise = ibstSearch right v\n>ibstSearch IBEmpty _ = False\n>\n<\/pre>\n
     This one should be pretty easy to read without much explanation. To be pedantic, I’ll walk through it quickly. If it’s a non-empty node, and the value in the node equals the value being searched for, return true. If the value in the node is bigger, then return the result of searching the left subtree; otherwise, return the result of searching the right subtree. If it’s an empty node, then the value isn’t there, so return false.<\/p>\n
    \n
     A binary search tree isn’t particularly useful if it can only hold integers. So as a first step
    \ntowards making it more real, we’d like to be able to store not just integers in the tree,
    \nbut any value for which the necessary comparisons (><\/code> and ==<\/code>) are
    \ndefined. There’s a typeclass for that, called “Ord<\/code>“, for Ordered<\/em>. So now let’s just rewrite IntBST<\/code> as a generic BST using typeclasses:<\/p>\n
    \n>data (Ord a) => GenBST a = GBNode a (GenBST a) (GenBST a)\n>                  | GBEmpty deriving (Show)\n<\/pre>\n
    The variable on the left<\/em> of the equal in the data type definition is
    \na type parameter. The type-class constraint preceding the name of the
    \nnew datatype means that the type parameter “a<\/code>” can only<\/em> be
    \ninstantiated by a type that is an instance of the type-class “Ord<\/code>“. The
    \nmethod implementations will barely change:<\/p>\n
    \n>gbstInsert :: (Ord a) => GenBST a -> a -> GenBST a\n>gbstInsert (GBNode i left right) v\n>        | i > v = GBNode i (gbstInsert left v) right\n>        | otherwise = GBNode i left (gbstInsert right v)\n>gbstInsert GBEmpty v = (GBNode v GBEmpty GBEmpty)\n>\n>gbstSearch :: (Ord a) => GenBST a -> a -> Bool\n>gbstSearch (GBNode k left right) v\n> \t    | k == v = True\n>        | k > v = gbstSearch left v\n>        | otherwise = gbstSearch right v\n>gbstSearch GBEmpty _ = False\n<\/pre>\n
     With that implementation of gbstInsert<\/code>, we can pretty much reuse the code to
    \ngenerate a sample instance:\t<\/p>\n
    \n>gtreeone = gbstInsert (gbstInsert (gbstInsert (gbstInsert (gbstInsert GBEmpty 3) 5) 2) 17) 10\n>gtreetwo = (gbstInsert (gbstInsert (gbstInsert (gbstInsert gtreeone 4) 6) 1) 9)\n<\/pre>\n
     Look what ghci says about those:<\/p>\n
    \n*Main*gt; gtreetwo\nGBNode 3 (GBNode 2 (GBNode 1 GBEmpty GBEmpty) GBEmpty) (GBNode 5 (GBNode 4 GBEmpty GBEmpty) (GBNode 17 (GBNode 10 (GBNode 6 GBEmpty (GBNode 9 GBEmpty GBEmpty)) GBEmpty) GBEmpty))\n*Main> :type gtreetwo\ngtreetwo :: GenBST Integer\n*Main> gbstSearch gtreetwo 17\nTrue\n*Main> gbstSearch gtreetwo 18\nFalse\n*Main> gbstSearch gtreetwo 1\nTrue\n*Main> gbstSearch gtreeone 1\nFalse\n*Main>\n<\/pre>\n
     We can use the new generic tree in exactly<\/em> the same way that we used the integer
    \nspecific one. We don’t need to declare types of expressions that use it. The compiler
    \nwill happily infer the type parameter, and just make everything work. But now we’re not
    \nrestricted to integers:<\/p>\n
    \n*Main> gbstInsert (gbstInsert (gbstInsert GBEmpty \"hi\") \"hello\") \"Salutations\"\nGBNode \"hi\" (GBNode \"hello\" (GBNode \"Salutations\" GBEmpty GBEmpty) GBEmpty) GBEmpty\n*Main> gbstInsert (gbstInsert (gbstInsert (gbstInsert GBEmpty \"hi\") \"hello\") \"S\nalutations\") \"Greetings\"\nGBNode \"hi\" (GBNode \"hello\" (GBNode \"Salutations\" (GBNode \"Greetings\" GBEmpty GBEmpty) GBEmpty) GBEmpty) GBEmpty\n*Main>\n<\/pre>\n
     I think that’s enough for one day. Next time, we’ll take our binary search tree, and look at using it for key\/value pairs, and maintaining tree balance.<\/p>\n","protected":false},"excerpt":{"rendered":"
    For this post, I’m doing a bit of an experiment. Haskell includes a “literate” syntax mode. In literate mode, and text that doesn’t start with a “>” sign is considered a comment. So this entire post can be copied and used as a source file; just save it with a name ending in `”.lhs”`. If […]<\/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-232","post","type-post","status-publish","format-standard","hentry","category-haskell"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-3K","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/232","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=232"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/232\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=232"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=232"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=232"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}