Advanced Functional Programming, assignment 3 - Haskell

gistfile1.hs

-- Peter Renström and Göran Nehlin
-- Advanced Functional Programming - Assignment 3 (Haskell)

-- 1.
-- Define an appropriate data type for binary search trees which uses strings
-- as keys.
--
-- Define a function insert k v t that inserts a key k with value v into the
-- tree t and returns the new tree.

data Tree k v = EmptyTree | Node k v (Tree k v) (Tree k v)
	deriving (Show, Read, Eq)

-- Creates a single node with two empty "legs"
singleton :: k -> v -> Tree k v
singleton k v = Node k v EmptyTree EmptyTree

-- Usage: 
-- *Main> insert "key" 10 (Node "key2" 15 EmptyTree EmptyTree)
insert :: (Ord k) => k -> v -> Tree k v -> Tree k v
insert k v EmptyTree = singleton k v
insert k v (Node a b left right)
	| k == a = Node a b left right
	| k < a = Node a b (insert k v left) right
	| k > a = Node a b left (insert k v right)

-- 2. 
-- Define a function that takes a list and returns a list of all ways to split
-- the list into two halves.
--
-- Example:
--
-- *Main> papercuts "hello"
-- [("","hello"),("h","ello"),("he","llo"),("hel","lo"),
--  ("hell","o"),("hello","")]

papercuts :: [a] -> [([a], [a])]
papercuts l = papercutsAux [] l

papercutsAux :: [a] -> [a] -> [([a], [a])]
papercutsAux a [] = [(a, [])]
papercutsAux a (x:b) =
	(a, x:b) : papercutsAux (a ++ [x]) b

-- 3.
-- Define a function that produces a list of all strings that can be
-- constructed using the letters 'a' and 'b'.
-- 
-- Example:
-- 
-- *Main> take 10 ablist
-- ["","a","b","aa","ba","ab","bb","aaa","baa","aba"]

ablist = [str | len <- [0..], str <- ablist' len] where
	ablist' 0 = [""]
	ablist' len =
		map ('a':) (ablist' (len - 1)) ++ map ('b':) (ablist' (len - 1))