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: "Learn You a Haskell" question (Frank)
2. Re: Data.Stream interleave implementation question
(Frerich Raabe)
3. Re: Disappointing thought on Haskell -- a simple space leak
on "insert" is hard bug to catch (Dimitri DeFigueiredo)
4. Re: Using Traversal as a kind of pointer (Elise Huard)
----------------------------------------------------------------------
Message: 1
Date: Mon, 18 Aug 2014 16:28:19 -0400
From: Frank <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] "Learn You a Haskell" question
Message-ID:
<ca+a3wkjn0zxca1f61cj8hvje43ummacij-ydjacak2tzjof...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
Thanks!
On Monday, August 18, 2014, Bob Ippolito <[email protected]> wrote:
> The definition of a Functor requires that exactly one of the type
> variables be free, which is why it's written as `Either a` instead of
> `Either a b`. Any fields that are not `b` must be simply passed through
> as-is by fmap. There could be a separate functor that would fmap over the
> Left, but there isn't (in the base package anyhow).
>
> There's a related Functor for `(,) a` where the Functor fmaps over the snd
> of the tuple, and the fst is left as-is.
>
> fmap (+1) ('a', 2) == ('a', 3)
> fmap (+1) (Right 2) == Right 3
> fmap (+1) (Left 'a') == Left 'a'
>
> Chris Done recently prototyped a fmap explorer that you might find useful:
> http://www.reddit.com/r/haskell/comments/2dok9w/functor_explorer/
>
> -bob
>
>
>
> On Mon, Aug 18, 2014 at 11:02 AM, Frank <[email protected]
> <javascript:_e(%7B%7D,'cvml','[email protected]');>> wrote:
>
>> Hi,
>> I'm reading "Learn You a Haskell..." and have a question about the
>> chapter "Making Our Own Types and Typeclasses". On the 'Functor'/'Either'
>> example, I feel completely lost. I don't see why the 'Left x' portion of
>> 'Functor (Either a)' is simply 'Left x' and the document is not exactly
>> clear. Any clarification would be most appreciated.
>>
>> Sincerely,
>> Frank D. Martinez
>>
>>
>> --
>> P.S.: I prefer to be reached on BitMessage at
>> BM-2D8txNiU7b84d2tgqvJQdgBog6A69oDAx6
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> <javascript:_e(%7B%7D,'cvml','[email protected]');>
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>>
>
--
P.S.: I prefer to be reached on BitMessage at
BM-2D8txNiU7b84d2tgqvJQdgBog6A69oDAx6
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140818/83fa38d9/attachment-0001.html>
------------------------------
Message: 2
Date: Mon, 18 Aug 2014 23:12:17 +0200
From: Frerich Raabe <[email protected]>
To: <[email protected]>
Subject: Re: [Haskell-beginners] Data.Stream interleave implementation
question
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8; format=flowed
On 2014-08-18 20:22, Curt McDowell wrote:
> Funny, I was trying the same Homework, implemented interleaveStreams using
> the same algorithm you did (taking one item from each stream per recursive
> call), and got the same result with the ruler function hanging. It was
> also
> fixed by changing interleaveStreams to take from just one stream per call
> and switch back and forth between streams.
I hit the same problem when I did the exercise. In fact, it made me post
this question on StackOverflow, asking about how pattern matching might
cause
the function to work differently:
http://stackoverflow.com/questions/25078598/why-would-using-head-tail-instead-of-pattern-matching-make-evaluation-terminate
I thought the answers were quite enlightening, if only to emphasize that
debugging this kind of problem is really difficult (to me). I only noticed
that not using pattern matching for the second argument of 'interleave'
helps
by accident...
--
Frerich Raabe - [email protected]
www.froglogic.com - Multi-Platform GUI Testing
------------------------------
Message: 3
Date: Mon, 18 Aug 2014 17:58:44 -0600
From: Dimitri DeFigueiredo <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Disappointing thought on Haskell -- a
simple space leak on "insert" is hard bug to catch
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Hi Heinrich,
Thanks so much! :-)
Wow! I was totally wrong on that one then. I got it that lazy evaluation
is the culprit here. Now, I am still a little uneasy about insert
producing a new version of the tree when it is not needed. Can't that
come back to bite me later depending on how I use it?
In your explanation, you say that "the old path is usually not
referenced anywhere, and can be garbage collected immediately."
I am a little uneasy about the "usually". Could you expand on that? What
if it is? Could that happen? Or does that just imply a bigger constant?
Thanks again,
Dimitri
Em 16/08/14 04:13, Heinrich Apfelmus escreveu:
> Dimitri DeFigueiredo wrote:
>> Here's a problem I just found with Haskell (and maybe functional
>> programming) that I would like to know how to avoid.
>>
>> Please don't get me wrong. I'm in *LUUV* with Haskell! :-)
>>
>>
>> Exercise 2.3 of Chris Okasaki's book "Purely Functional Data
>> Structures" shows that something as simple as an insert function in a
>> binary tree can cause a space leak in Haskell. (and other functional
>> languages as well)
>>
>> Here's a simple tree type:
>>
>> data Tree a = Empty
>> | MkTree (Tree a) a (Tree a)
>>
>> Here's the version of insert with the space leak:
>>
>> -- ** SPACE LEAK! ** version
>> -- this version unnecessarily copies the path to the inserted element
>> even if
>> -- the same element is already present in the tree.
>> -- a million insertions of the same element will cause a million trees
>> -- to exist whereone would suffice.
>>
>> treeInsert :: Ord a => a -> Tree a -> Tree a
>> treeInsert e Empty = MkTree Empty e Empty
>> treeInsert e t@(MkTree a x b) | e > x = MkTree a x (treeInsert e b)
>> | e < x = MkTree (treeInsert e a) x b
>> | otherwise = t
>>
>> Here's a version without the space leak:
>>
>> treeInsert :: Ord a => a -> Tree a -> Tree a
>> treeInsert e t = case (treeInsert' e t) of
>> Nothing -> t
>> Just x -> x
>> where
>> treeInsert' :: Ord a => a -> Tree a -> Maybe (Tree a)
>> treeInsert' e Empty = return $ MkTree Empty e Empty
>> treeInsert' e (MkTree a x b) | e > x = do {r <-
>> treeInsert' e b; return $ MkTree a x r}
>> | e < x = do {r <-
>> treeInsert' e a; return $ MkTree r x b}
>> | otherwise = Nothing
>>
>>
>> This is so tricky that I think it is worth questioning whether
>> Haskell is helping here. First, just spotting that the first version
>> leads to a space leak is not trivial. Second, the fix is so much
>> uglier than the original version. It is disappointing to have to
>> write it!
>>
>> Questions:
>> 1) ** Is there a warning sign that would easily flag this space leak? **
>> 2) Is there a simpler fix?
>
> The really tricky thing here is that the space leak is not what you
> think it is. :)
>
> When you use the tree in an ephemeral fashion, the issue is *not* that
> the path to the element is being copied, because the old path is
> usually not referenced anywhere, and can be garbage collected
> immediately. Asymptotically, this has no impact on space usage.
>
> Instead, the issue is that the tree operations are not "completed".
> Inserting the same element a thousand times without inspecting the
> tree afterwards, you will get a tree that contains a huge unevaluated
> subtree, like
>
> MkTree (treeInstert 'a' (treeInsert 'a' ...)) 'f' Empty
>
> What your supposed fix actually does is that it fully evaluates the
> subtrees as well.
>
> An easier way to achieve this to use a "strictness annotation" in the
> data type, which is done via the `!` symbol:
>
> data Tree a = Empty
> | MkTree !(Tree a) a !(Tree a)
>
> This data type may not have any unevaluated subtrees. Try it and see
> whether it solves your problem.
>
>
> In general, lazy evaluation is a trade-off: It makes some programs
> simpler to write, but the price is that the cost model becomes more
> difficult, both for time and for space usage. Cost models that you may
> know from eager languages do not apply anymore.
>
> For reasoning about time usage, Okasaki introduces the "debit
> method",w hich you've certainly read about. Another exposition can be
> found in [1].
>
> For reasoning about space, I recommend an approach that I like to call
> "space invariants" [2]. The key problem with the space leak above is
> that the semantics of a tree -- which elements it contains -- no
> longer coincides with the size of its representation -- an expression
> which may be only partially evaluated. For things like infinite lists,
> e.g. [1..], this is actually great! But for other things like finite
> maps, this may lead to unexpected space usage. The remedy is to
> enforce a "space invariant", which is a guarantee that links the
> semantics and the size of the representation. An example would be "A
> tree in WHNF uses only as much space as the leaves it contains (+
> skeleton)". The annotion `!` is one way to enforce these invariants.
>
>
> [1]: http://apfelmus.nfshost.com/articles/debit-method.html
> [2]: http://apfelmus.nfshost.com/blog/2013/08/21-space-invariants.html
>
>
> Best regards,
> Heinrich Apfelmus
>
> --
> http://apfelmus.nfshost.com
>
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
------------------------------
Message: 4
Date: Tue, 19 Aug 2014 10:37:48 +0200
From: Elise Huard <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Using Traversal as a kind of pointer
Message-ID:
<CAHfyCq=0g0nya8tmf49nyfebcxyhsgsi5otwtjivhjg3_o0...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Thanks for the example! I found another example of filtered here
http://www.haskellforall.com/2013/05/program-imperatively-using-haskell.html
I'm aware that filtered traversals should only ever be used with
functions that will not change the number of elements filtered.
Thank you!
Elise
On 18 August 2014 16:03, Daniel Trstenjak <[email protected]> wrote:
>
> Hi Elise,
>
>> thanks for your answer. That looks like something that might work -
>> however, having never worked with Optics, I'm not entirely sure
>> whether I'm doing it right, getting an error:
>
> oh sorry, there has to be a 'traversed' before the 'filtered'.
>
>> Also, may I ask what the '&' is in your proposed solution?
>
> The '&' is just applying a lens to a variable.
>
>
> So here's a working example:
>
> {-# LANGUAGE Rank2Types #-}
>
> import Control.Lens
>
> type Background = Int
> type Lifeform = Int
> type Player = Int
>
>
> data World = World Background [Lifeform] deriving (Show)
>
>
> lifeforms :: Lens' World [Lifeform]
> lifeforms = lens getLifeforms setLifeforms
> where
> getLifeforms (World _ lifeforms) = lifeforms
> setLifeforms (World bg _) lifeforms = World bg lifeforms
>
>
> colliding :: Player -> Traversal' [Lifeform] Lifeform
> colliding player = traversed . filtered (== player)
>
>
> If you load this into ghci und can write:
>
> > World 1 [1, 2] & lifeforms . colliding 1 %~ (+ 10)
> > World 1 [11,2]
>
>
> Greetings,
> Daniel
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 74, Issue 16
*****************************************
