<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
</head>
<body text="#000000" bgcolor="#FFFFFF">
Hi,<br>
<i><small><br>
Disclaimer: I have been learning Haskell for a month and there
are still several things about this wonderful language I know
nothing of, so please bear with me. Also, I apologize for this
(somewhat) long mail.</small></i><br>
<br>
I came across this article:
<a class="moz-txt-link-freetext" href="http://unriskinsight.blogspot.co.at/2014/06/fast-functional-goats-lions-and-wolves.html">http://unriskinsight.blogspot.co.at/2014/06/fast-functional-goats-lions-and-wolves.html</a>
a couple of days ago. This compares performance of solving a problem
(which I will get to) using the functional constructs alone in
languages like C++11 and Java 8.<br>
Since, Haskell is my first foray into FP, I thought I should try
solving this in Haskell.<br>
<br>
So the problem at hand is this: There is a magical forest which has
only Lions, Wolves and Goats.<br>
Lions are stronger than Wolves which are in turn stronger than
Goats. Each strong animal is capable of eating a weaker animal,
which also in turn transforms the '<i>eater</i>' into an animal
which was not involved.<br>
<i>i.e.</i> If a Lion eats a Wolf it gets transformed into a Goat.
If a Wolf eats a Sheep it gets transformed into a Lion.<br>
<br>
Below are the two versions of the code I came up with to solve this.
Neither of them converge to the 'endStates' even after about 15
minutes. So there is definitely something wrong with what I have
done. But after banging my head on the keyboard for more then a day
with this, I would appreciate some pointers or help.<br>
<br>
<font face="Courier New, Courier, monospace">-- version 1<br>
import Data.List<br>
<br>
data Animal = Lion Int | Wolf Int | Goat Int<br>
deriving (Show, Eq)<br>
<br>
type Forest = [Animal]<br>
<br>
-- lions f = count 0 f<br>
-- where<br>
-- count acc [] = acc<br>
-- count acc ((Lion a):as) = acc + a + (count acc as)<br>
-- count acc (_:as) = acc + (count acc as)<br>
<br>
-- wolfs f = count 0 f<br>
-- where<br>
-- count acc [] = acc<br>
-- count acc ((Wolf a):as) = acc + a + (count acc as)<br>
-- count acc (_:as) = acc + (count acc as)<br>
<br>
-- goats f = count 0 f<br>
-- where<br>
-- count acc [] = acc<br>
-- count acc ((Goat a):as) = acc + a + (count acc as)<br>
-- count acc (_:as) = acc + (count acc as)<br>
<br>
lions [Lion l, Wolf w, Goat g] = l<br>
wolfs [Lion l, Wolf w, Goat g] = w<br>
goats [Lion l, Wolf w, Goat g] = g<br>
<br>
--Invalid eat calls are returned with [], to denote termination<br>
eat :: Forest -> Animal -> Animal -> Forest<br>
eat f (Lion _) (Goat le) =<br>
if (l >= le && g >= le) then [Lion (l-le), Wolf
(w+le), Goat (g-le)] else []<br>
where<br>
l = lions f<br>
w = wolfs f<br>
g = goats f<br>
eat f (Lion _) (Wolf le) =<br>
if (l >= le && w >= le) then [Lion (l-le), Wolf
(w-le), Goat (g+le)] else []<br>
where<br>
l = lions f<br>
w = wolfs f<br>
g = goats f<br>
eat f (Wolf _) (Goat we) =<br>
if (w >= we && g >= we) then [Lion (l+we), Wolf
(w-we), Goat (g-we)] else []<br>
where<br>
l = lions f<br>
w = wolfs f<br>
g = goats f<br>
eat _ _ _ = []<br>
<br>
lionEatGoat :: Forest -> Forest<br>
lionEatGoat f = eat f (Lion 0) (Goat 1)<br>
<br>
lionEatWolf :: Forest -> Forest<br>
lionEatWolf f = eat f (Lion 0) (Wolf 1)<br>
<br>
wolfEatGoat :: Forest -> Forest<br>
wolfEatGoat f = eat f (Wolf 0) (Goat 1)<br>
<br>
meal :: Forest -> [Forest]<br>
meal [] = []<br>
meal f@[Lion l, Wolf w, Goat g]<br>
| endState f = []<br>
| l == 0 = [f] ++ weg<br>
| w == 0 = [f] ++ leg<br>
| g == 0 = [f] ++ lew<br>
| (l /= 0) && (w /= 0) && (g /= 0) = [f] ++ leg
++ lew ++ weg<br>
| otherwise = []<br>
where<br>
leg = meal $ lionEatGoat f<br>
lew = meal $ lionEatWolf f<br>
weg = meal $ wolfEatGoat f<br>
<br>
endState :: Forest -> Bool<br>
endState f = if ((l == 0 && g == 0) ||<br>
(l == 0 && w == 0) ||<br>
(w == 0 && g == 0)) then<br>
True<br>
else<br>
False<br>
where<br>
l = lions f<br>
w = wolfs f<br>
g = goats f<br>
<br>
endStates = filter endState<br>
<br>
main = do<br>
putStrLn $ show $ endStates $ meal [Lion 6, Wolf 55, Goat 17]</font><br>
<br>
I thought using the ADT was causing the performance issue and
reverted to using a plain 3-termed list which holds <font
face="Courier New, Courier, monospace">[Lion count, Wolf Count,
Sheep Count] :: [Int]<br>
</font><font face="Courier New, Courier, monospace"><br>
-- version 2<br>
import Data.List<br>
<br>
lionEatGoat :: [Int] -> [Int]<br>
lionEatGoat [l,w,g] = [l-1,w+1,g-1]<br>
<br>
lionEatWolf :: [Int] -> [Int]<br>
lionEatWolf [l,w,g] = [l-1,w-1,g+1]<br>
<br>
wolfEatGoat :: [Int] -> [Int]<br>
wolfEatGoat [l,w,g] = [l+1,w-1,g-1]<br>
<br>
meal :: [Int] -> [[Int]]<br>
meal [] = []<br>
meal f@[l, w, g]<br>
| endState f = []<br>
| l == 0 = (f:weg:(meal weg))<br>
| w == 0 = (f:leg:(meal leg))<br>
| g == 0 = (f:lew:(meal lew))<br>
| (l /= 0) && (w /= 0) && (g /= 0) =<br>
(f:leg:lew:weg:(meal leg ++ meal lew ++ meal weg))<br>
| otherwise = []<br>
where<br>
leg = lionEatGoat f<br>
lew = lionEatWolf f<br>
weg = wolfEatGoat f<br>
<br>
endState :: [Int] -> Bool<br>
endState [l,w,g] = if ((l == 0 && g == 0) ||<br>
(l == 0 && w == 0) ||<br>
(w == 0 && g == 0)) then<br>
True<br>
else<br>
False<br>
endStates = filter endState<br>
<br>
main = do<br>
putStrLn $ show $ endStates $ meal [Lion 6, Wolf 55, Goat 17]</font><br>
<br>
This is still extremely slow, without the program ever terminating.<br>
<br>
Can someone please tell me what I am doing wrong. <br>
<br>
-Elric<br>
</body>
</html>