Is the equivalent of Haskell's Foldable and Traversable simply a sequence in Clojure?

Question

In Haskell we see Foldable and Traversable landing in Haskell prelude.

These both do operations on sequences.

Prelude Data.Sequence> map (\n -> replicate n 'a') [1,3,5]
["a","aaa","aaaaa"]
Prelude Data.Sequence> fmap (\n -> replicate n 'a') (1 <| 3 <| 5 <| empty)
fromList ["a","aaa","aaaaa"]

My question is is the equivalent of Haskell's Foldable and Traversable simply a sequence in Clojure?

Assumptions:

• I realise that the equivalent of fmap in Haskell is m-fmap in Clojure.

Answer 1

No. Whilst any kind of Functor representing finite sequences of elements will be Traversable (hence Foldable), there are plenty of other structures which are Traversable, but which aren't sequence-like, in that they don't have an obvious notion of concatenation. There will be a way to obtain the sequence of contained elements, but the structure may consist of more than just that sequence.

What Traversable f means, in effect, is that structures with type f x contain finitely many elements of type x, and that there is some way to traverse the structure visiting each element of x exactly once. So things like "terms in a syntax, seen as containing variables" can be Traversable.

data Term x
  = Var x
  | Val Integer
  | Add (Term x) (Term x)

instance Traversable Term where
  traverse f (Var x)    = pure Var <*> f x
  traverse f (Val i)    = pure (Val i)
  traverse f (Add s t)  = pure Add <*> traverse f s <*> traverse f t

You can always use traverse to do operations on all elements. We get fmap by taking pure = id and <*> to be ordinary application.

instance Functor Term where
  fmap = fmapDefault

where

fmap :: (x -> y) -> Term x -> Term y

implements simultaneous renaming.

Meanwhile, the Foldable instance

instance Foldable Term where
  foldMap = foldMapDefault

takes pure to give the neutral element of some monoid and <*> to the combining operation, so we get reduce-like operations. E.g.,

foldMap (:[]) :: Term x -> [x]

gives the list of variables occurring in a term. That is we can always obtain the sequence of elements from Traversable data, but the data might have structure other than those elements. Terms have structure other than variables (their Vals and Adds), and it's not so clear what "cons" means for syntax trees.

So, while more structures than sequences are Traversable, the Traversable interface offers you fewer sequence-like operations. The point of Traversable is to generalize map-like and reduce-like operations, not to capture list-ness.

Answer 2

I'd like to point out the Haskell wiki documentation on Foldable and Traversable.

First of all, Foldable and Traversable are two different type classes. As for Foldable, the comments made by the wiki page seem to suggest that it is pretty much the same as a Clojure sequence. Every Foldable has a representation as a list:

toList :: Foldable a => [a]
toList a = foldr (:) [] a

and (correct me if I'm wrong) it seems that folding over the structure is the same as folding over the associated list, i.e.:

foldr f b a = foldr f b (toList a)

In this equation the foldr on the left is the generic version whereas the one on the right is the one on lists.

The main difference between Haskell and Clojure here is that Clojure requires you to apply the toList function yourself to convert the data structure to a sequence before folding/reducing it. For flat data structures (i.e. lists, vectors, hash maps...) toList is just the identity function so you don't see it. On the other hand for something like trees you would need to call a function like tree-seq before folding it.