Why is Foldable a superclass of Crosswalk?

[cspollard]

There is no reference to Foldable in the default definitions, so is there a more fundamental reason?

The reason I ask is because I have a data type that appears to fit the Crosswalk shape, but its Foldable instance is, frankly, not meaningful, and I would prefer not to implement it. However, I wonder if this also makes the Crosswalk instance bogus.

[phadej]

I cannot come with Crosswalkable constainer, which ins't Foldable. #78 is an example (which we cannot have in the lib unfortunately).

[Zemyla]

If we create a free Align, and then specialize its type to Const m, then it's effectively a list of ms, which can be subsequently mappended up. The join law doesn't come up, because a law-abiding Crosswalk can only call fonce for each a inside it. That's why Foldable is a prerequisite, and why foldMapCrosswalk works.

[Zemyla]

I've actually almost proven that every Crosswalk is Traversable, even.

{-# LANGUAGE GADTs #-}

import Data.These
import Data.Align
import Unsafe.Coerce

data FreeAlign f a where
  Nil :: FreeAlign f a
  Lift :: (u -> a) -> f u -> FreeAlign f a
  AlignWith :: (These u v -> a) -> FreeAlign f u -> FreeAlign f v -> FreeAlign f a

instance Functor (FreeAlign f) where
  fmap _ Nil = Nil
  fmap f (Lift g fu) = Lift (f . g) fu
  fmap f (AlignWith g au av) = AlignWith (f . g) au av

instance SemiAlign (FreeAlign f) where
  alignWith = AlignWith

instance Align (FreeAlign f) where
  nil = Nil

-- Try to lower a FreeAlign to an Applicative. The main difference between Align and Applicative is that
-- Align's unit, nil, has no attached value, whereas Applicative's, pure, does. This causes a bit of
-- difficulty.
tryLowerFAA :: Applicative f => FreeAlign f a -> Maybe (f a)
tryLowerFAA Nil = Nothing
tryLowerFAA (Lift g f) = Just (fmap g f)
tryLowerFAA (AlignWith g au av) = case tryLowerFAA au of
  Nothing -> tryLowerFAA (fmap (g . That) av)
  Just fu -> Just $ case tryLowerFAA av of
    Nothing -> fmap (g . This) fu
    Just fv -> liftA2 (\u v -> g (These u v)) fu fv

-- This is almost a proof, but it relies on containers that report being empty to crosswalk actually
-- being empty, and thus the parameter being phantom.
traverseCrosswalk :: (Crosswalk t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverseCrosswalk f t = case tryLowerFAA (crosswalk (Lift id . f) t) of
  Just ft -> ft
  Nothing -> pure (unsafeCoerce t) -- Dubious?

-- By contrast, foldMapCrosswalk works without any issue.
foldMapCrosswalk :: (Monoid m, Crosswalk t) => (a -> m) -> t a -> m
foldMapCrosswalk f t = case tryLowerFAA (crosswalk (Lift id . Const . f) t) of
  Just (Const m) -> m
  Nothing -> mempty

So there we go. Every Crosswalk is also Foldable, and also morally Traversable.