<div dir="ltr"><div>That is surprising. I would have expected an O(1) way to retrieve some value at random.<br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Mar 8, 2015 at 12:59 AM, Heinrich Apfelmus <span dir="ltr"><<a href="mailto:apfelmus@quantentunnel.de" target="_blank">apfelmus@quantentunnel.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">Thomas Bach wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Jeffrey Brown <<a href="mailto:jeffbrown.the@gmail.com" target="_blank">jeffbrown.the@gmail.com</a>> writes:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
head $ Data.Set.toList S. If I do that, am I correct that Haskell will<br>
not try to convert all of S to a list; instead it will only convert<br>
one element, and then return it, and leave the rest of the list<br>
unevaluated?<br>
</blockquote>
<br>
This is how toList from Data.Set.Base is defined in containers-0.5.0:<br>
<br>
{-----------------------------<u></u>------------------------------<u></u>---------<br>
  Lists<br>
------------------------------<u></u>------------------------------<u></u>--------}<br>
-- | /O(n)/. Convert the set to a list of elements. Subject to list fusion.<br>
toList :: Set a -> [a]<br>
toList = toAscList<br>
<br>
-- | /O(n)/. Convert the set to an ascending list of elements. Subject to list fusion.<br>
toAscList :: Set a -> [a]<br>
toAscList = foldr (:) []<br>
<br>
The buzzword you are looking for is list fusion:<br>
<br>
<a href="http://stackoverflow.com/questions/10945429/haskell-list-fusion-where-is-it-needed" target="_blank">http://stackoverflow.com/<u></u>questions/10945429/haskell-<u></u>list-fusion-where-is-it-needed</a><br>
</blockquote>
<br></span>
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.<br>
<br>
Jeffrey, if you want to pick a single element from a `Set`, I would recommend the functions `findMin` or `findMax`. The former satisfies<br>
<br>
    Data.Set.findMin = head . Data.Set.toList<br>
<br>
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.)<br>
<br>
<br>
  [1]: <a href="https://hackhands.com/modular-code-lazy-evaluation-haskell/" target="_blank">https://hackhands.com/modular-<u></u>code-lazy-evaluation-haskell/</a><br>
<br>
<br>
Best regards,<br>
Heinrich Apfelmus<br>
<br>
--<br>
<a href="http://apfelmus.nfshost.com" target="_blank">http://apfelmus.nfshost.com</a><div class="HOEnZb"><div class="h5"><br>
<br>
______________________________<u></u>_________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" target="_blank">http://mail.haskell.org/cgi-<u></u>bin/mailman/listinfo/beginners</a><br>
</div></div></blockquote></div><br></div>