Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/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: State Monad stack example (Animesh Saxena)
2. Laziness to efficiently get one element from a set
(Jeffrey Brown)
3. Re: Laziness to efficiently get one element from a set
(Thomas Bach)
4. Re: Laziness to efficiently get one element from a set
(Jeffrey Brown)
----------------------------------------------------------------------
Message: 1
Date: Sat, 07 Mar 2015 17:34:23 +0000 (GMT)
From: Animesh Saxena <[email protected]>
To: [email protected], The Haskell-Beginners Mailing
List - Discussion of primarily beginner-level topics related to
Haskell <[email protected]>
Subject: Re: [Haskell-beginners] State Monad stack example
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"; Format="flowed"
Thanks for the links, I am able to get my head around this a bit.?
Here's my simple question
1. In the stack example what is the state. As per my understanding the state is
the new stack.
If above statement is correct than by definition of >>=
? (>>=) :: State s a -> (a -> State s b) -> State s b
push 3 stack?
This returns ((), newstack1)
Now in this case the state or context is newstack1 which has to be passed to
the next function if i apply >>=.
push 3 stack >>= pop newstack1
This might make sense coz I am shoving (or binding) the state to the pop
function. State in this case is the stack which is being passed around or
shoved around. Problem is pop doesn't need "a" argument like the definition of
(>>=) indicates. It can very well produce a new state or return ?a new state.?
So if state = stack then this makes sense to me, where am i wrong...??
push 3 stack >>= pop newstack1
On Mar 06, 2015, at 09:09 PM, "Sumit Sahrawat, Maths & Computing, IIT (BHU)"
<[email protected]> wrote:
I won't comment on what state exactly is, but you can read up on that and gain
some intuition here:
https://en.wikibooks.org/wiki/Haskell/Understanding_monads/State
It's helpful to implement it using a pen and paper, and consider how the state
flows and gets transformed.
According to the below example,
? stackManip stack =
? ? let?((), newStack1) = push 3 stack
? ? ? ? (a, newStack2) ?= pop newStack1
? ? in pop newStack2
We get,
? push :: a -> Stack a -> ((), Stack a) ? ?-- Assuming 'Stack a' is a defined
datatype
? pop ?:: Stack a -> (a, Stack a) ? ? ? ? ?-- Representing a stack with
elements of type 'a'
Thus,
? ? push 3 >>= pop
~~ ?(Stack a -> ((), Stack a)) >>= (Stack a -> (a, Stack a)) ? ? ? ? ? ? ? {
Replacing by types }
Bind (>>=) has the type, (for "State s")
? (>>=) :: State s a -> (a -> State s b) -> State s b
This is a type mismatch. The conversion to do syntax is at fault here.
First, you must write the computation using bind (>>=), and then convert to
do-notation.
On 7 March 2015 at 10:12, Animesh Saxena <[email protected]> wrote:
I am trying to relate the state monad to a stack example and somehow found it
easy to get recursively confused!
instance Monad (State s) where
? ? return x = State $ \s -> (x,s)
? ? (State h) >>= f = State $ \s -> let (a, newState) = h s
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (State g) = f a
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?in g newState
Considering the stack computation
stackManip stack = let?
? ? ? ? ? ? ? ((), newStack1) = push 3 stack
? ? ? ? ? ? ? (a, newStack2) = pop newStack1
? ? ? ? ? ? ? ?in pop newStack2
in do notation this would become?
do ?
? ?push 3 ?
? ?a <- pop ?
? ?pop
If I consider the first computation push 3 >>= pop and try to translate it to
the definition there are problems....
Copy paste again, I have?
? ? (State h) >>= f = State $ \s -> let (a, newState) = h s
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (State g) = f a
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?in g newState
f is the push function to which we are shoving the old state. I can't exactly
get around to what exactly is the state computation h? Ok assuming it's
something which gives me a new state, but then thats push which is function f.?
Then push is applied to a which is assuming 3 in this case. This gives me a new
state, which I would say newStack1 from the stockManip above.
Then somehow I apply g to newState?? All the more confusion. Back to the
question what exactly is state computation and how is it different from f? It
seems to be the same function?
-Animesh
? ? ? ? ? ? ? ? ? ? ? ? ? ?
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
--
Regards
Sumit Sahrawat
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150307/c4dd6f17/attachment-0001.html>
------------------------------
Message: 2
Date: Sat, 7 Mar 2015 13:52:08 -0800
From: Jeffrey Brown <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: [Haskell-beginners] Laziness to efficiently get one element
from a set
Message-ID:
<caec4ma3ekjhbb3aavsbvcmkfhgpordzu4bfdmlrqlck03yp...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hi,
Suppose S is a big set, and I'd like to access just a single element from
it. The only natural way I've come up with to do that is this: head $
Data.Set.toList S. If I do that, am I correct that Haskell will not try to
convert all of S to a list; instead it will only convert one element, and
then return it, and leave the rest of the list unevaluated?
Thanks,
Jeff
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150307/451d4a88/attachment-0001.html>
------------------------------
Message: 3
Date: Sun, 8 Mar 2015 00:49:43 +0100
From: Thomas Bach <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Laziness to efficiently get one
element from a set
Message-ID: <[email protected]>
Content-Type: text/plain
Jeffrey Brown <[email protected]> writes:
> head $ Data.Set.toList S. If I do that, am I correct that Haskell will
> not try to convert all of S to a list; instead it will only convert
> one element, and then return it, and leave the rest of the list
> unevaluated?
This is how toList from Data.Set.Base is defined in containers-0.5.0:
{--------------------------------------------------------------------
Lists
--------------------------------------------------------------------}
-- | /O(n)/. Convert the set to a list of elements. Subject to list fusion.
toList :: Set a -> [a]
toList = toAscList
-- | /O(n)/. Convert the set to an ascending list of elements. Subject to list
fusion.
toAscList :: Set a -> [a]
toAscList = foldr (:) []
The buzzword you are looking for is list fusion:
http://stackoverflow.com/questions/10945429/haskell-list-fusion-where-is-it-needed
Regards
Thomas Bach.
------------------------------
Message: 4
Date: Sat, 7 Mar 2015 16:11:29 -0800
From: Jeffrey Brown <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Laziness to efficiently get one
element from a set
Message-ID:
<caec4ma0hi3jhkrddeqaddvu1dtc-tdrjd3ebg8zhwc_nvw5...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Fantastic! Thanks, Thomas!
On Sat, Mar 7, 2015 at 3:49 PM, Thomas Bach <[email protected]>
wrote:
> Jeffrey Brown <[email protected]> writes:
>
> > head $ Data.Set.toList S. If I do that, am I correct that Haskell will
> > not try to convert all of S to a list; instead it will only convert
> > one element, and then return it, and leave the rest of the list
> > unevaluated?
>
> This is how toList from Data.Set.Base is defined in containers-0.5.0:
>
> {--------------------------------------------------------------------
> Lists
> --------------------------------------------------------------------}
> -- | /O(n)/. Convert the set to a list of elements. Subject to list fusion.
> toList :: Set a -> [a]
> toList = toAscList
>
> -- | /O(n)/. Convert the set to an ascending list of elements. Subject to
> list fusion.
> toAscList :: Set a -> [a]
> toAscList = foldr (:) []
>
> The buzzword you are looking for is list fusion:
>
>
> http://stackoverflow.com/questions/10945429/haskell-list-fusion-where-is-it-needed
>
> Regards
>
> Thomas Bach.
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150307/0199f749/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 81, Issue 28
*****************************************
