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` instance: 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. -- Viktor.