<div dir="ltr">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.</div><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Mar 8, 2015 at 10:57 AM, Jeffrey Brown <span dir="ltr"><<a href="mailto:jeffbrown.the@gmail.com" target="_blank">jeffbrown.the@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><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="HOEnZb"><div class="h5"><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>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><div><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>
</div></div><br>_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
<br></blockquote></div><br></div>