Tagged data in Haskell (SICP 2.4.2)

I have a copy of sicp, or as it is also known, The Wizard<br>Book.11 Structure and Interpretation of Computer Programs; Abelson and<br>Sussman; mit Press; 1996. This book is widely praised, but I can&rsquo;t take the<br>time to work my way through all of it. However, sometimes I jump into parts of<br>it that look interesting. Today, we&rsquo;ll see how to support multiple<br>representations of data through tagging.

This article is written in Haskell throughout, but at the start it will look a<br>lot like the Lisp code in sicp. I have intentionally tried to recreate the<br>sicp solution as closely as possible, including dynamic typing and all. See<br>the appendix if you&rsquo;re curious how it works.

Complex numbers in two forms

Complex numbers can be stored in their rectangular form, where there&rsquo;s a real<br>and an imaginary part. They can also be stored in polar form, where there&rsquo;s a<br>magnitude and an angle. The authors ask us to imagine that two people have been<br>working on a library for mathematics, but ended up choosing different ways to<br>store complex numbers. How can they write their code so that they don&rsquo;t have to<br>agree on one way to store the data?

Abelson and Sussman propose a tagged representation, where the data of the<br>complex numbers are paired with a tag, which indicates to the implementation<br>what representation is being used. They suggest the following functions to<br>attach a tag, as well as inspect tagged data.

As a last reminder, this is Haskell code, but written in Lisp style to mimic the<br>solution in sicp as closely as possible.

In[1]:<br>-- | Tag a value as having a particular representation.<br>attach_tag tag contents =<br>(cons tag contents)

-- | Extract the type tag from a tagged value.<br>type_tag datum =<br>(if_ (is_pair datum)<br>(car datum)<br>(error "Bad tagged datum"))

-- | Extract the value from a tagged value.<br>contents datum =<br>(if_ (is_pair datum)<br>(cdr datum)<br>(error "Bad tagged datum"))

This code uses cons in the Lisp sense, i.e. it creates a pair of two values,<br>with a left hand side, known as the car of the pair, and a right hand side,<br>known as the cdr of the pair.

With these, we can check if a complex number is stored in its rectangular or<br>polar representation by inspecting its tag.

In[2]:<br>is_rectangular z =<br>(eq (type_tag z) (quote "rectangular"))

is_polar z =<br>(eq (type_tag z) (quote "polar"))

To create a complex number in either rectangular or polar form, we create a cons<br>cell with the coordinates, and tag that cell with the appropriate symbol.

In[3]:<br>make_rectangular re im =<br>(attach_tag (quote "rectangular") (cons re im))

make_polar r a =<br>(attach_tag (quote "polar") (cons r a))

If we have the rectangular coordinates for a complex number, we can extract the<br>real and imaginary part easily, too. These functions assume we have peeled off<br>the tag, and that the data is in the correct format.

In[4]:<br>real_part_rectangular z = (car z)<br>imag_part_rectangular z = (cdr z)

Similarly, we can easily extract the polar coordinates from a complex number<br>stored in its polar form. These implementations are the same as the above,<br>because these functions are supposed to be run after we have verified the tag is<br>correct, and the tag has been peeled off.

In[5]:<br>magnitude_polar z = (car z)<br>angle_polar z = (cdr z)

If we want to extract polar coordinates from a complex number stored in<br>rectangular form, or vice versa, we&rsquo;ll have to do some trigonometry.

In[6]:<br>magnitude_rectangular z =<br>(sqrt_ (add_ (square_ (real_part_rectangular z))<br>(square_ (imag_part_rectangular z))))

angle_rectangular z =<br>(atan_ (imag_part_rectangular z)<br>(real_part_rectangular z))

real_part_polar z =<br>(mul_ (magnitude_polar z) (cos_ (angle_polar z)))

imag_part_polar z =<br>(mul_ (magnitude_polar z) (sin_ (angle_polar z)))

These functions also assume a particular representation, with the tag peeled<br>off. But, now that we have all of the above, we can write our first generic<br>functions, i.e. those that can work on either representation. They&rsquo;ll do this by<br>inspecting the tag and then performing the right operation depending on what<br>representation is indicated by the tag.

These generic functions will extract the respective coordinates for complex<br>numbers regardless of their underlying representation, by dispatching on the<br>type tag.

In[7]:<br>real_part z =<br>(if_ (is_rectangular z)<br>(real_part_rectangular (contents z))<br>(if_ (is_polar z)<br>(real_part_polar (contents z))<br>(error "Unknown type")))

imag_part z =<br>(if_ (is_rectangular z)<br>(imag_part_rectangular (contents z))<br>(if_ (is_polar z)<br>(imag_part_polar (contents z))<br>(error "Unknown type")))

magnitude z =<br>(if_ (is_rectangular z)<br>(magnitude_rectangular (contents z))<br>(if_ (is_polar z)<br>(magnitude_polar (contents z))<br>(error "Unknown type")))

angle z =<br>(if_ (is_rectangular z)<br>(angle_rectangular (contents z))<br>(if_ (is_polar z)<br>(angle_polar (contents z))<br>(error "Unknown type")))

Given these, the two people no longer have to agree on how they should store<br>complex...