Programming Praxis – An Early LISP Program

In today’s Programming Praxis exercise, our goal is to write a function to un-nest a list. Let’s get started, shall we?

Since Haskell is statically typed, the concept of nested lists is a bit more difficult than in Lisp, which is dynamically typed. In a regular list in Haskell all elements must be of the same type, which in a nested list is not the case. There are various ways around this, so I will give three different solutions.

Some pragmas and an import for the third and second solution, respectively:

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies,
             FlexibleInstances, UndecidableInstances #-}

import Data.Dynamic

Solution 1: create a datatype for nested lists.

First, we define a nested list:

data List a = E a | L [List a]

Collapsing this list is then a fairly trivial task: just collapse each sublist recursively.

collapse_data :: List a -> [a]
collapse_data (E x) = [x]
collapse_data (L xs) = collapse_data =<< xs

Solution 2: Use dynamic typing.

Just because Haskell is a static language doesn’t mean it can’t do dynamic typing. The only downside is that entering the list is a tad laborious with toDyns all over the place.

collapse_dyn :: Typeable a => Dynamic -> [a]
collapse_dyn x = maybe (maybe [] return $ fromDynamic x)
                       (collapse_dyn =<<) (fromDynamic x)

Solution 3: Tuples

Haskell has a way of defining lists that have elements of different types: tuples. The downside is that tuples of different lengths are considered completely different types, and it is therefore necessary to define every function for every possible tuple length. This can be automated by using Template Haskell, but I won’t go into that here. The advantage of this method is that the list literals look almost exactly like the Lisp ones (with the addition of some commas).

First, we define a typeclass for values that can be collapsed.

class Collapsible a b | a -> b where
    collapse :: a -> [b]

Next, we describe how to collapse a tuple. As mentioned, the code for 3-tuples and longer can be generated using Template Haskell.

instance (Collapsible a c, Collapsible b c) => Collapsible (a, b) c where
    collapse (a, b) = collapse a ++ collapse b

We also need to describe how to collapse literals. For production use, the other literals like Int and Float should be defined as well.

instance Collapsible Char Char where
    collapse c = [c]

Some tests to see if everything is working properly:

main :: IO ()
main = do
    print $ collapse_data (L[L[L[L[E 'a', E 'b'], L [L [E 'c']]],
                               L [L [E 'd', L [E 'e', E 'f']],
                                  L [E 'g'], L [L [E 'h']]]]]) == "abcdefgh"
    print $ collapse_dyn (toDyn [toDyn [toDyn 'a', toDyn [toDyn 'b',
              toDyn [toDyn 'c', toDyn [toDyn 'd', toDyn [toDyn 'e']]], 
              toDyn 'f', toDyn [toDyn 'g',
              toDyn [toDyn 'h', toDyn 'j']]]]]) == "abcdefghj"
    print $ collapse (((((('a'), 'b'), 'c'), 'd'), 'e')) == "abcde"

Yep. The first two methods are short to implement but make the actual lists less concise, the third is the other way round. Choose whichever option you prefer.

About these ads

Tags: , , , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: