search

jaspervdj / psqueues

Priority Search Queues in three different flavors for Haskell
https://hackage.haskell.org/package/psqueues
Other
64 stars 24 forks source link

Functor instance invalid #10

Open treeowl opened 8 years ago

treeowl commented 8 years ago

The Elem constructor is strict in v, which is bogus for a Functor. The constructor should be made lazy, and the forcing done by other functions.

meiersi-da commented 8 years ago

You are right that it is overly strict for fmap (f . g) = fmap f . fmap g to hold in the case of bottoms. For example fmap (const () . const undefined) == fmap (const ()) . fmap (const undefined) does not hold. However, I do wonder in what cases that is that an actual problem? I wonder in particular, as I really like my data-structures to be unable to contain any thunk if they are in WHNF. This makes a common class of space leaks just go away.

Put differently I currently believe that it is OK or even preferable for data structures that do not model control to be this strict. It is clear to me that for Applicative and Monad we want to have the lazy versions that can deal with bottoms. It is not yet clear to me, what we loose from an overly strict Functor that is not an Applicative.