A Simple Exercise
"Given three sets of characters, build all the possible words of 3 characters, with the first character from the first set, the second character from the second set, and the last character from the last set."{-# LANGUAGE OverloadedStrings #-}
module Combinatorial where
set1 :: [Char]
set1 = "ab"
set2 :: [Char]
set2 = "12"
set3 :: [Char]
set3 = set1
The Recursive Solution
In a classical imperative solution we would write three nested loops trying all combinations. In Haskell we can replace loops with recursion.allWordsOf3Chars :: [Char] -> [Char] -> [Char] -> [String]
allWordsOf3Chars set1 set2 set3 = combine1 set1 set2 set3
where
combine1 [] _ _ = []
combine1 (c1:cs) set2 set3 = combine2 c1 set2 set3 ++ combine1 cs set2 set3
combine2 _ [] _ = []
combine2 c1 (c2:cs) set3 = combine3 c1 c2 set3 ++ combine2 c1 cs set3
combine3 _ _ [] = []
combine3 c1 c2 (c3:cs) = [[c1, c2, c3]] ++ combine3 c1 c2 cs
test1 = allWordsOf3Chars set1 set2 set3
> test1
["a1a","a1b","a2a","a2b","b1a","b1b","b2a","b2b"]
The KISS Solution
In Haskell list comprehension has a combinatorial semantic, and so we can write simplyallWordsOf3Chars' set1 set2 set3
= [ [c1, c2, c3] | c1 <- set1, c2 <- set2, c3 <- set3 ]
isOk1 = test1 == (allWordsOf3Chars' set1 set2 set3)
> isOk1
True
The KISS solution is very easy to read, and very fast to write. A good selling point for the Haskell language.The Advanced Solution
In Haskell theApplicative
instance of List
, has a combinatorial semantic, so we can writeallWordsOf3Chars'' set1 set2 set3
= (\c1 c2 c3 -> [c1, c2, c3] ) <$> set1 <*> set2 <*> set3
isOk2 = test1 == (allWordsOf3Chars'' set1 set2 set3)
> isOk2
True
The Extended Exercise
We can generalize the first problem, passing a list of sets of chars, instead of only 3 sets.The Extended Recursive Solution
In an imperative language, generalizing the solution is not simple, because we have a number of loops that is not fixed.Generalizing the Haskell recursive solution is apparently simpler, because we start already from a recursion, but in practice it is rather hard to figure out the right algorithm.
combineWords :: [String] -> [String]
combineWords sets = combine [] sets
where
combine :: String -> [String] -> [String]
combine decidedPart [] = [decidedPart]
combine decidedPart (set1:sets) = choices decidedPart set1 sets
choices :: String -> String -> [String] -> [String]
choices decidedPart currentSet otherSets =
concatMap (\c -> combine (decidedPart ++ [c]) otherSets) currentSet
isOk3 = test1 == (combineWords [set1, set2, set3])
> isOk3
True
This algo works because:- it has a main loop on each set
- the inner loop selecting one character from the set, calls again the main loop function for obtaining all the possible solutions with the remaining sets
Writing this algo required too much time respect the initial planned time, and I can not declare that writing it in Haskell is a very easy task.
The extended KISS Solution
Apparently the previous KISS solution based on list comprehension, can not be extended easily to the new version of the problem.The Extended Advanced Solution
I were in a meetup, so I asked help to someone more knowledgeable than me, and his solution was shockingcombineWords''' :: [String] -> [String]
combineWords''' sets = sequence sets
isOk4 = test1 == (combineWords''' [set1, set2, set3])
> isOk4
True
I'm not completely sure of the reason this algo works. I need to study better Haskell, and the magic behind sequence
. >:t sequence
sequence :: (Traversable t, Monad m) => t (m a) -> m (t a)
In any case this solution shows the power of Haskell abstractions.The Pragmatic Solution
At this point, I'm not completely satisfied from the Haskell language:- the recursive solution is too time-consuming and difficult to obtain
- the advanced solution is very short, but too deep for my taste
We have a combinatorial problem. For sure an iconic language for expressing and solving combinatorial problems is Prolog. But Haskell supports very well Domain Specific Languages (DSL), and so I can use a Prolog-like DSL language also in Haskell. In this case the
MonadPlus
applied to lists, is the right instance to use. Note that in case of very complex combinatorial problems, the best solution is probably using high-performance packages like LogicGrowsOnTree, but in this case it is overkill.combineWords'''' :: [String] -> [String]
combineWords'''' sets = combine [] sets
where
combine decidedPart [] = return decidedPart
combine decidedPart (set1:sets) = do
c <- set1
combine (decidedPart ++ [c]) sets
isOk5 = test1 == combineWords'''' [set1, set2, set3]
> isOk5
True
Don't ask me why, but this version of the function was very fast and natural to write for me, and very readable. It is based on a simple constraint, and only one recursive call. Probably because a single recursion is easier to understand than the dual recursion version, and because I were accustomed to Prolog.Also the
MonadPlus
version of the first version of the problem is very natural to writeallWordsOf3Chars'''' :: [Char] -> [Char] -> [Char] -> [String]
allWordsOf3Chars'''' set1 set2 set3 = do
c1 <- set1
c2 <- set2
c3 <- set3
return [c1, c2, c3]
isOk6 = test1 == allWordsOf3Chars'''' set1 set2 set3
> isOk6
True
Conclusions
If some problems are hard to solve in Haskell, probably there exists some DSL able to express and solve them in a more natural way. The advantage of studying a new DSL, it is that after the initial investment of time, all problems in the same domain can be solved faster.Probably there is also a payoff in studying better
Applicative
, Traversable
, and sequence
function, but for this problem, the MonadPlus
solution seems to me a good balance between simplicity and terseness of the code.
No comments:
Post a Comment