Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Lions, Wolves and Goats (Elric)
2. Re: Lions, Wolves and Goats (Elric)
3. Re: Lions, Wolves and Goats (Elric)
----------------------------------------------------------------------
Message: 1
Date: Fri, 13 Jun 2014 11:37:11 -0400
From: Elric <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Lions, Wolves and Goats
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"; Format="flowed"
Thank You Ariis,
I was using nub in a wrong way, like so:
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 = nub $ meal $ ionEatGoat f
lew = nub $ meal $ lionEatWolf f
weg = nub $ meal $ wolfEatGoat f
After looking at your solution, I realized I was essentially generating
every possible state, and THEN trying to remove the duplicates, whereas
in your solution at each step you remove possible duplicates states of
the forest and propagate to the next step only from there.
Thank You,
Praveen
On 06/08/2014 02:33 AM, Francesco Ariis wrote:
> On Sat, Jun 07, 2014 at 08:04:09PM -0400, Elric wrote:
>> Hi,
>>
>> 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.
>>
> Hello Elric,
> I gave a go at the problem, managed to get a result (23).
> I attach the .hs file (not my best Haskell, but hopefully clear enough).
>
> The crucial point in my solution lies in this lines:
>
> carnage :: [Forest] -> [Forest]
> let wodup = nub aa in
> -- etc. etc.
>
> Which means after every iteration I call |nub| on my list of possible
> states; nub is a function from |Data.List| and removes duplicate
> elements from a list.
>
> If I omit that nub call, the program doesn't reach a solution (as it
> is computationally quite inefficient). I think that's the problem
> with your versions.
>
> Let me know if this helps
>
>
>
>
>
>
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140613/021b1d24/attachment-0001.html>
------------------------------
Message: 2
Date: Fri, 13 Jun 2014 11:51:23 -0400
From: Elric <[email protected]>
To: Ben Gamari <[email protected]>, [email protected]
Subject: Re: [Haskell-beginners] Lions, Wolves and Goats
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"; Format="flowed"
Thank You Ben,
Your solution is really neat. I was trying to create the infix 'eat'
function when I was thinking of implementing this in Haskell. But I
completely forgot about being able to use the Record syntax to do this.
I am not sure about the purpose of !Int, but that is something for me to
read more and learn :)
Thank You,
Elric
On 06/08/2014 04:52 PM, Ben Gamari wrote:
> Elric <[email protected]> writes:
>
>> 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./
>>
> ...
>> 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.
>>
> For one, you don't appear to be removing duplicates from the search set
> resulting in a blow-up in your search space.
>
>> 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]
>>
> Your problem here isn't the use of ADTs, it's the use of lists. Why not
> instead define a forest as follows?
>
> data Forest = Forest { wolfs, lions, goats :: !Int }
>
> Note how I used a strictness annotation !Int here to ensure that the
> compiler unboxes these members (at least with GHC >= 7.8), which is
> almost certainly what you want in this case.
>
> Anyways, I took a quick stab at the problem myself. My approach can be
> found here[1]. Performance isn't great (a bit better than Javascript)
> but then again the code is pretty much as naive as one could get. I'm
> sure things could be improved.
>
> Cheers,
>
> - Ben
>
>
> [1] https://gist.github.com/anonymous/e4a2ccd8df05255d5ed5
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140613/cc900bb8/attachment-0001.html>
------------------------------
Message: 3
Date: Fri, 13 Jun 2014 11:54:29 -0400
From: Elric <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Lions, Wolves and Goats
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"; Format="flowed"
Thank You Bob,
I learnt quite a bit from your solution. I have been restricting myself
to Lists so far. I think I will have to start exploring other data
structures like Sets in Haskell as well. :)
Thank You,
Elric
On 06/08/2014 03:41 PM, Bob Ippolito wrote:
> Here's another approach that more closely models what's going on in
> the C++ version. I defined an ordNub rather than using nub as nub is
> O(n^2) as it only requires Eq.
>
> https://gist.github.com/etrepum/5bfedc8bbe576f89fe09
>
> import qualified Data.Set as S
> import Data.List (partition)
> import System.Environment (getArgs)
>
> data LWG = LWG { _lion, _wolf, _goat :: {-# UNPACK #-} !Int }
> deriving (Show, Ord, Eq)
>
> lionEatGoat, lionEatWolf, wolfEatGoat :: LWG -> LWG
> lionEatGoat (LWG l w g) = LWG (l - 1) (w + 1) (g - 1)
> lionEatWolf (LWG l w g) = LWG (l - 1) (w - 1) (g + 1)
> wolfEatGoat (LWG l w g) = LWG (l + 1) (w - 1) (g - 1)
>
> stableState :: LWG -> Bool
> stableState (LWG l w g) = length (filter (==0) [l, w, g]) >= 2
>
> validState :: LWG -> Bool
> validState (LWG l w g) = all (>=0) [l, w, g]
>
> possibleMeals :: LWG -> [LWG]
> possibleMeals state =
> filter validState .
> map ($ state) $ [lionEatGoat, lionEatWolf, wolfEatGoat]
>
> ordNub :: Ord a => [a] -> [a]
> ordNub = S.toList . S.fromList
>
> endStates :: [LWG] -> [LWG]
> endStates states
> | not (null stable) = stable
> | not (null unstable) = endStates (concatMap possibleMeals unstable)
> | otherwise = []
> where (stable, unstable) = partition stableState (ordNub states)
> main :: IO ()
> main = do
> [l, w, g] <- map read `fmap` getArgs
> mapM_ print . endStates $ [LWG l w g]
>
>
>
> On Sat, Jun 7, 2014 at 11:33 PM, Francesco Ariis <[email protected]
> <mailto:[email protected]>> wrote:
>
> On Sat, Jun 07, 2014 at 08:04:09PM -0400, Elric wrote:
> > Hi,
> >
> > 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.
> >
>
> Hello Elric,
> I gave a go at the problem, managed to get a result (23).
> I attach the .hs file (not my best Haskell, but hopefully clear
> enough).
>
> The crucial point in my solution lies in this lines:
>
> carnage :: [Forest] -> [Forest]
> let wodup = nub aa in
> -- etc. etc.
>
> Which means after every iteration I call |nub| on my list of possible
> states; nub is a function from |Data.List| and removes duplicate
> elements from a list.
>
> If I omit that nub call, the program doesn't reach a solution (as it
> is computationally quite inefficient). I think that's the problem
> with your versions.
>
> Let me know if this helps
>
>
>
>
>
>
>
> _______________________________________________
> Beginners mailing list
> [email protected] <mailto:[email protected]>
> http://www.haskell.org/mailman/listinfo/beginners
>
>
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140613/7a7e16c3/attachment-0001.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 72, Issue 13
*****************************************
