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: Laziness to efficiently get one element from a set
(Jeffrey Brown)
2. Re: Laziness to efficiently get one element from a set
(Bob Ippolito)
----------------------------------------------------------------------
Message: 1
Date: Sun, 8 Mar 2015 10:57:01 -0700
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:
<CAEc4Ma2FU7trg=wtO3ab-WFAjepPTRb0EvLuMqy-Dp7iL=a...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
That is surprising. I would have expected an O(1) way to retrieve some
value at random.
On Sun, Mar 8, 2015 at 12:59 AM, Heinrich Apfelmus <
[email protected]> wrote:
> 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
>
>
> _______________________________________________
> 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/542ec0bc/attachment-0001.html>
------------------------------
Message: 2
Date: Sun, 8 Mar 2015 11:19:07 -0700
From: Bob Ippolito <[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:
<cacwmpm8s0annwspej_oprxqhurx33-xtojgbuh0fwht+rn5...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
It would be possible to return the value at the root of the tree in O(1)
time, but there's no function for this and the constructor isn't exported
so you can't implement it yourself.
On Sun, Mar 8, 2015 at 10:57 AM, Jeffrey Brown <[email protected]>
wrote:
> That is surprising. I would have expected an O(1) way to retrieve some
> value at random.
>
> On Sun, Mar 8, 2015 at 12:59 AM, Heinrich Apfelmus <
> [email protected]> wrote:
>
>> 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
>>
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> 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/b8da2d4c/attachment-0001.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 32
*****************************************
