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

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@quantentunnel.de> wrote:

Thomas Bach wrote:

...

Jeffrey Brown 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@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners