[Haskell-beginners] Laziness to efficiently get one element from a set

[Bob Ippolito]

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 <jeffbrown.the at gmail.com>
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 <
> apfelmus at quantentunnel.de> wrote:
>
>> Thomas Bach wrote:
>>
>>> Jeffrey Brown <jeffbrown.the at gmail.com> 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
>> Beginners at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> 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.html>