[Haskell-cafe] Haskell's "historical futurism" needs better writing, not better tools

Viktor Dukhovni 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 mailing list