Posts Tagged ‘nested’

Programming Praxis – An Early LISP Program

March 1, 2011

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.