Skip to content

Instantly share code, notes, and snippets.

@cdepillabout
Last active Aug 29, 2015
Embed
What would you like to do?
explanation of combination function in Haskell
{-# LANGUAGE ScopedTypeVariables #-}
-- | This is an explanation of a combination function written in Haskell
-- from http://rosettacode.org/wiki/Combinations#Dynamic_Programming_2
module Main where
-- | Adds a @a@ to the beginning of every list inside the list of lists.
-- However, if the list of lists is just an empty list, return an empty
-- list.
--
-- >>> append 3 []
-- []
-- >>> append 3 [[1]]
-- [[3,1]]
-- >>> append 3 [[], [1], [4,5,6]]
-- [[3], [3,1], [3,4,5,6]]
--
append :: forall a . a -- ^ element to add
-> [[a]] -- ^ list to list of @a@ to add element to
-> [[a]] -- ^ resulting list of list
append x partial_accum = map append_x partial_accum
where
append_x :: [a] -> [a]
append_x list = x : list
-- | Prepend the element @a@ to every sub-sub list (which would be a list
-- that is two lists deep). Don't do anything to elements that are just
-- list-of-lists.
--
-- Also prepends an empty list to the beginning.
--
-- >>> g 0 []
-- [[]]
-- >>> g 0 [[]]
-- [[],[]]
-- >>> g 0 [[[]]]
-- [[],[[0]]]
-- >>> g 0 [[[1,2,3]]]
-- [[],[[0,1,2,3]]]
-- >>> g 0 [[[1,2,3],[4,5,6]],[[7,8,9]],[]]
-- [[],[[0,1,2,3],[0,4,5,6]],[[0,7,8,9]],[]]
g :: forall a . a -> [[[a]]] -> [[[a]]]
g x accum = map helper accum_with_empty_list
where
-- Return our accumulator with an empty list appended on the
-- front.
accum_with_empty_list :: [[[a]]]
accum_with_empty_list = [] : accum
-- | Prepend the element @a@ to all sublists in @[[a]]@.
--
-- >>> helper [[1,2,3,4], [5,6], [7,8,9], []]
-- [[0,1,2,3,4], [0,5,6], [0,7,8,9], [0]] -- where @x@ is 0
helper :: [[a]] -> [[a]]
helper acc = append x acc
f :: a -> [[[a]]] -> [[[a]]]
f x accum = zipWith (++) (g x accum) accum
-- | This produces a list of list of lists. The first element is a list
-- containing an empty list, and all subsequent elements are empty lists.
--
-- >>> head double_empty_list_plus_infinite_empty
-- [[]]
-- >>> tail double_empty_list_plus_infinite_empty
-- [[], [], [], [], ...]
-- >>> take 5 double_empty_list_plus_infinite_empty
-- [[[]], [], [], [], []]
--
double_empty_list_plus_infinite_empty :: [[[a]]]
double_empty_list_plus_infinite_empty = [[]] : [] : [] : [] : repeat []
combBySize :: [a] -> [[[a]]]
combBySize list = foldr f double_empty_list_plus_infinite_empty list
-- | This is our new combining function (that hopefully will be easier to
-- understand...).
comb :: Int -> [a] -> [[a]]
comb m xs = combBySize xs !! m
-- | This is the original combining function.
comb' :: Int -> [a] -> [[a]]
comb' m xs = combsBySize' xs !! m
where
combsBySize' = foldr f' ([[]] : repeat [])
f' x next = zipWith (++) (map (map (x:)) ([]:next)) next
main :: IO ()
main = do
print $ comb 3 ['a', 'b', 'c', 'd']
print $ comb' 3 ['a', 'b', 'c', 'd']
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment