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: Most important Functional Methods (Erik Price)
2. Re: Most important Functional Methods (Patrick Mylund Nielsen)
3. Lions, Wolves and Goats (Elric)
4. Re: Lions, Wolves and Goats (Francesco Ariis)
----------------------------------------------------------------------
Message: 1
Date: Sat, 7 Jun 2014 05:40:09 -0700
From: Erik Price <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Most important Functional Methods
Message-ID:
<cad+x7c8hd-hpg_hh-p3gvufhbw8fpsug4emwpjgjnkr5vv6...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Saturday, June 7, 2014, Richard Seldon <[email protected]> wrote:
> Hello,
>
> I have a general question, not specific to Haskell although I am learning
> Haskell as I ask this question..
>
> Please can someone provide consensus on the most important functional
> methods in their view.
>
> I read somewhere that having map, reduce, filter, mergeAll, and zip pretty
> much means everything else can be derived.
You might be interested in reading this excellent introductory article on
folds, which are Haskell's equivalent to what some languages call reduce:
http://www.cs.nott.ac.uk/~gmh/fold.pdf
It shows how many of the basic higher-order functions (such as map, filter,
etc) can be derived from a fold.
e
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140607/0cc99837/attachment-0001.html>
------------------------------
Message: 2
Date: Sat, 7 Jun 2014 08:51:00 -0400
From: Patrick Mylund Nielsen <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Most important Functional Methods
Message-ID:
<CAEw2jfzezjrEL+9DtU_DC-3a+FJNhk+ayCTst9hy_o72M=-x...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Sat, Jun 7, 2014 at 8:40 AM, Erik Price <[email protected]> wrote:
>
>
> On Saturday, June 7, 2014, Richard Seldon <[email protected]> wrote:
>
>> Hello,
>>
>> I have a general question, not specific to Haskell although I am learning
>> Haskell as I ask this question..
>>
>> Please can someone provide consensus on the most important functional
>> methods in their view.
>>
>> I read somewhere that having map, reduce, filter, mergeAll, and zip
>> pretty much means everything else can be derived.
>
>
> You might be interested in reading this excellent introductory article on
> folds, which are Haskell's equivalent to what some languages call reduce:
>
> http://www.cs.nott.ac.uk/~gmh/fold.pdf
>
> It shows how many of the basic higher-order functions (such as map,
> filter, etc) can be derived from a fold.
>
> e
>
In fact, concatMap (flatMap) is defined like so:
-- | Map a function over a list and concatenate the results.concatMap
:: (a -> [b]) -> [a] -> [b]concatMap f =
foldr ((++) . f) []
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140607/e9b05568/attachment-0001.html>
------------------------------
Message: 3
Date: Sat, 07 Jun 2014 20:04:09 -0400
From: Elric <[email protected]>
To: [email protected]
Subject: [Haskell-beginners] Lions, Wolves and Goats
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"; Format="flowed"
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140607/eac8d220/attachment-0001.html>
------------------------------
Message: 4
Date: Sun, 8 Jun 2014 08:33:56 +0200
From: Francesco Ariis <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Lions, Wolves and Goats
Message-ID: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: carnage.hs
Type: text/x-haskell
Size: 1226 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140608/e4e52128/attachment.hs>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 72, Issue 6
****************************************
