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

[Heinrich Apfelmus]

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