[Haskell-cafe] Haskell's "historical futurism" needs better writing, not better tools
ietf-dane at dukhovni.org
Fri Oct 1 06:41:04 UTC 2021
On Thu, Sep 30, 2021 at 09:14:36PM -0400, Viktor Dukhovni wrote:
> > Is there a sensible (useful, lawful) Foldable instance which has no
> > 'fromList'?
Another salient counter-example, is the Foldable instance of `Map k`,
which sequences only the *values* `v` stored in a `Map k v`, forgetting
the keys `k`. There is therefore no:
fromList :: [v] -> Map k v
that could undo:
toList :: Map k v -> [v]
and for that we'd need the Map spine (key set) its `Traversable`
fromValueList :: Ord k => Map k () -> [a] -> Map k a
fromValueList = evalState . traverse f where
f :: () -> State [v] v
f _ = get >>= \ !s -> head s <$ put (tail s)
Basically, containers can have a non-trivial "shape" that `toList`
"flattens", so it is a one-way operation.
Switching subtopics to the "Chirality" section, I added it in response
to a criticism that earlier text was inaccurate for structures that do
not support efficient left-to-right iteration (if you like, have an
inefficient or possibly divergent `toList` that might take a long time
or forever to return the left-most element).
If there's a general feeling that accepting the suggestion to be more
accurate was a mistake, the exposition could indeed be shorter if it
were fair to assume that all Foldable structures of interest are
"left-handed" (can quickly return the left-most element). And that
while one can define structures that violate this assumption, they're
not a good fit for Foldable and not worthy of explication.
More information about the Haskell-Cafe