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

[Jeffrey Brown]

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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150308/542ec0bc/attachment.html>