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. Re: Laziness to efficiently get one element from a set
(Heinrich Apfelmus)
3. Strange behavior of program (m00nlight)
----------------------------------------------------------------------
Message: 1
Date: Sun, 08 Mar 2015 11:55:09 +0800
From: Animesh Saxena <[email protected]>
To: 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="windows-1252"
Ok I got the confusion clear, I was referring to the wrong definitions of push
and pop
pop = Stack $ (\x:xs) -> (x,xs)
push a = State $ \xs -> ((), xs)
Now the do operation makes sense coz now I can relate all this to simple
monads?.
(>>=) :: Monad m => m a -> (a -> m b) -> m b
Where m = state s being shoved around!
-Animesh
> On Mar 8, 2015, at 1:34 AM, Animesh Saxena <[email protected]> wrote:
>
> 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
>> <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]
>> <mailto:[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] <mailto:[email protected]>
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>> <http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners>
>>
>>
>>
>>
>> --
>> Regards
>>
>> Sumit Sahrawat
>> _______________________________________________
>> Beginners mailing list
>> [email protected] <mailto:[email protected]>
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>> <http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners>
> _______________________________________________
> 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/20150308/b3f6ca00/attachment-0001.html>
------------------------------
Message: 2
Date: Sun, 08 Mar 2015 09:59:47 +0100
From: Heinrich Apfelmus <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Laziness to efficiently get one
element from a set
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8; format=flowed
Thomas Bach 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
Actually, I don't think that list fusion is appropriate here. The
`foldr` used in the definition of `toAscList` is from the `Foldable`
type class, and implemented specifically for the `Set` data type. It's
not the usual fold on lists.
Jeffrey, if you want to pick a single element from a `Set`, I would
recommend the functions `findMin` or `findMax`. The former satisfies
Data.Set.findMin = head . Data.Set.toList
so you will get the same element as in your original approach. This
time, however, you can be sure that it takes O(log n) time, whereas in
the approach using `head`, it depends on the internals of the
implementation of `foldr` whether it will take time O(n) or O(log n) or
something in between. (In particular, it depends on how lazy the
implementation of `foldr` for `Set` is. See [1] for more on lazy
evaluation in this / a similar context.)
[1]: https://hackhands.com/modular-code-lazy-evaluation-haskell/
Best regards,
Heinrich Apfelmus
--
http://apfelmus.nfshost.com
------------------------------
Message: 3
Date: Sun, 8 Mar 2015 18:59:57 +0800 (CST)
From: m00nlight <[email protected]>
To: "The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell" <[email protected]>
Subject: [Haskell-beginners] Strange behavior of program
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
Hi Haskellers,
I encounter an strange behavior of haskell program recently. The following is
my program
```haskell
main = do
_ <- getLine
arr1 <- getLine
_ <- getLine
arr2 <- getLine
let a = map (read :: String -> Int) (words arr1)
b = map (read :: String -> Int) (words arr2)
putStrLn $ show $ (foldl (*) 1 a)
putStrLn $ show $ a == [1,2,4,8,32,64,128,256,512,1024,2048,4906,8192]
putStrLn $ show $ (foldl (*) 1
[1,2,4,8,32,64,128,256,512,1024,2048,4906,8192])
```
With the input test file as following:
```test.in
13
1 2 4 8 32 64 128 256 512 1024 2048 4906 8192
9
1 3 9 27 81 243 729 2187 6561
```
The output is as:
```output
0
True
185343439719667835347140608
```
In fact, from the program, we know that a is equal to list
[1,2,4,8,32,64,128,256,512,1024,2048,4906,8192] ,
but the product of a and the literal list is different.
Can anyone tell me why?
Thanks
--m00nlight
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150308/27bf09ca/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 29
*****************************************
