Hi,

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.

I came across this article: http://unriskinsight.blogspot.co.at/2014/06/fast-functional-goats-lions-and-wolves.html 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.
Since, Haskell is my first foray into FP, I thought I should try solving this in Haskell.

So the problem at hand is this: There is a magical forest which has only Lions, Wolves and Goats.
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 'eater' into an animal which was not involved.
i.e. If a Lion eats a Wolf it gets transformed into a Goat. If a Wolf eats a Sheep it gets transformed into a Lion.

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.

-- version 1
import Data.List

data Animal = Lion Int | Wolf Int | Goat Int
            deriving (Show, Eq)

type Forest = [Animal]

-- lions f = count 0 f
--   where
--     count acc [] = acc
--     count acc ((Lion a):as) = acc + a + (count acc as)
--     count acc (_:as) = acc + (count acc as)

-- wolfs f = count 0 f
--   where
--     count acc [] = acc
--     count acc ((Wolf a):as) = acc + a + (count acc as)
--     count acc (_:as) = acc + (count acc as)
   
-- goats f = count 0 f
--   where
--     count acc [] = acc
--     count acc ((Goat a):as) = acc + a + (count acc as)
--     count acc (_:as) = acc + (count acc as)

lions [Lion l, Wolf w, Goat g] = l
wolfs [Lion l, Wolf w, Goat g] = w
goats [Lion l, Wolf w, Goat g] = g

--Invalid eat calls are returned with [], to denote termination
eat :: Forest -> Animal -> Animal -> Forest
eat f (Lion _) (Goat le) =
  if (l >= le && g >= le) then [Lion (l-le), Wolf (w+le), Goat (g-le)] else []
  where
    l = lions f
    w = wolfs f
    g = goats f
eat f (Lion _) (Wolf le) =
  if (l >= le && w >= le) then [Lion (l-le), Wolf (w-le), Goat (g+le)] else []
  where
    l = lions f
    w = wolfs f
    g = goats f
eat f (Wolf _) (Goat we) =
  if (w >= we && g >= we) then [Lion (l+we), Wolf (w-we), Goat (g-we)] else []
  where
    l = lions f
    w = wolfs f
    g = goats f
eat _ _ _ = []
                                                                        
lionEatGoat :: Forest -> Forest
lionEatGoat f = eat f (Lion 0) (Goat 1)

lionEatWolf :: Forest -> Forest
lionEatWolf f = eat f (Lion 0) (Wolf 1)

wolfEatGoat :: Forest -> Forest
wolfEatGoat f = eat f (Wolf 0) (Goat 1)

meal :: Forest -> [Forest]
meal [] = []
meal f@[Lion l, Wolf w, Goat g]
  | endState f = []
  | l == 0 = [f] ++ weg
  | w == 0 = [f] ++ leg
  | g == 0 = [f] ++ lew
  | (l /= 0) && (w /= 0) && (g /= 0) = [f] ++ leg ++ lew ++ weg
  | otherwise = []
  where
    leg = meal $ lionEatGoat f
    lew = meal $ lionEatWolf f
    weg = meal $ wolfEatGoat f

endState :: Forest -> Bool
endState f = if ((l == 0 && g == 0) ||
                 (l == 0 && w == 0) ||
                 (w == 0 && g == 0)) then
               True
             else
               False
  where
    l = lions f
    w = wolfs f
    g = goats f
               
endStates = filter endState
 
main = do
  putStrLn $ show $ endStates $ meal [Lion 6, Wolf 55, Goat 17]

I thought using the ADT was causing the performance issue and reverted to using a plain 3-termed list which holds [Lion count, Wolf Count, Sheep Count] :: [Int]

-- version 2
import Data.List
                                                                        
lionEatGoat :: [Int] -> [Int]
lionEatGoat [l,w,g] = [l-1,w+1,g-1]

lionEatWolf :: [Int] -> [Int]
lionEatWolf [l,w,g] = [l-1,w-1,g+1]

wolfEatGoat :: [Int] -> [Int]
wolfEatGoat [l,w,g] = [l+1,w-1,g-1]

meal :: [Int] -> [[Int]]
meal [] = []
meal f@[l, w, g]
  | endState f = []
  | l == 0 = (f:weg:(meal weg))
  | w == 0 = (f:leg:(meal leg))
  | g == 0 = (f:lew:(meal lew))
  | (l /= 0) && (w /= 0) && (g /= 0) =
    (f:leg:lew:weg:(meal leg ++ meal lew ++ meal weg))
  | otherwise = []
  where
    leg = lionEatGoat f
    lew = lionEatWolf f
    weg = wolfEatGoat f

endState :: [Int] -> Bool
endState [l,w,g] = if ((l == 0 && g == 0) ||
                       (l == 0 && w == 0) ||
                       (w == 0 && g == 0)) then
                     True
                   else
                     False
endStates = filter endState
 
main = do
  putStrLn $ show $ endStates $ meal [Lion 6, Wolf 55, Goat 17]

This is still extremely slow, without the program ever terminating.

Can someone please tell me what I am doing wrong.

-Elric