11

The wiki page says both classes deal with container operations, with Foldable being a class of containers that have foldr defined over them, and for Functor it's fmap.

However, what is the fundamental difference between types that are Foldable and types that are Functors?

The wiki hints at this distinction:

The class [Foldable] does not require Functor superclass in order to allow containers like Set or StorableVector

But I'm still not sure why a Set couldn't be mapped over to obtain another set, if I'm interpreting that correctly.

corazza
  • 31,222
  • 37
  • 115
  • 186

5 Answers5

12

Foldable and Functor offer two separate abstractions for types with structures that can be folded (or reduced) and mapped over, respectively.

A Foldable holds values that can be enumerated and combined together1. One can think of a Foldable as something that can be turned into a list (toList :: Foldable f => f a -> [a]). Alternatively, one can think of Foldables as structures whose values can be combined monoidally: (Foldable t, Monoid m) => (a -> m) -> t a -> m (of course, this requires the ability to enumerate them).

Functors, on the other hand, are structures that allow one to "lift" a function (a -> b) to apply to the as held by the structure (fmap :: (a -> b) -> (f a -> f b)). fmap must preserve the structure being mapped over: a tree must have the same shape before and after, a list must have the same number of elements in the same order, Nothing can't be turned into something, and so on. On the other hand, Foldables do not need to preserve this structure; the whole point is to discard the structure and produce a new one.

The Wiki refers to the fact that there is no way to supply a typeclass constraint to fmap. fmap :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b does not unify with the type defined by the class, fmap :: (a -> b) -> f a -> f b, which has no constraints. This makes an instance for Set impossible to write.

However, this is just a language implementation issue and not a deeper mathematic statement about sets. The real reason that Foldable does not have a Functor superclass is simply that there are Foldable instances which are not Functor instances.

  1. "Hold" is a bit loose and is intended to be interpreted in the "Functors are containers" sense where Proxy s a holds zero a's, Identity a holds one a, Maybe a holds zero or one a, b -> a holds |b| a's, and so on.
Community
  • 1
  • 1
Rein Henrichs
  • 15,437
  • 1
  • 45
  • 55
8

Suppose I have xs :: Set Int and I want to map the function putStrLn over it. This will be a problem because IO () doesn't have an Ord instance, so there's no way to figure out how to insert those actions into the result set. The type of fmap leaves no room for constraints on the type argument to the Functor.

IO also provides an example of something that's a Functor but that there isn't any meaningful way to foldMap.

It's worth mentioning that Foldable and Functor come together in the Traversable class, which gives substantially more power than either.

dfeuer
  • 48,079
  • 5
  • 63
  • 167
  • Why do you need `Ord` to figure out how to insert those actions into the resulting set? Wouldn't you only need `Eq`, and for example `==` could always be `False` for any two `IO ()`. – corazza Oct 15 '15 at 00:02
  • @jcora, it's impossible to implement an *efficient* set using just `Eq`. And making a dummy instance of `Eq` for `IO` would break all the expectations programmers have about what `==` means. – dfeuer Oct 15 '15 at 00:07
  • 2
    Whether you need `Eq` or `Ord` misses the point, of course. The point is that you can't have *any* typeclass constraints. – Rein Henrichs Oct 15 '15 at 00:13
  • @ReinHenrichs, I think it's useful to point out why any particular constraint on `fmap` could be harmful. – dfeuer Oct 15 '15 at 00:17
  • 1
    @jcora An `==` that always returns false isn't a valid equality relation (which requires that a thing is equal to itself). If you did it anyway, it would be useless to use as the basis of a Set, since it implies that when testing membership of an item in a set the item would never be equal to anything in the set, and thus the membership test would always return false. Which means that to stay consistent any such set must be empty; you can't even retrieve an item from it because any resulting item would fail the membership test and so actually isn't in the set after all. – Ben Oct 15 '15 at 00:58
  • @Ben Yes yes, I know, I literally just wrote that off the top of my head without thinking. Such `==` would sort of make sense if two variables couldn't refer to the same `IO ()` tho, for example each `printStrLn` result *should* really be added to the Set as it's a new action, no matter what gets printed. – corazza Oct 15 '15 at 15:47
7

Set and StorableVector are functors, you can indeed map functions over them.

But not any kind of function. For instance, you can't map (+) over a StorableArray of numbers: this would give an array of functions, and these are not storable.

So, these functors are not (endo-)functors on all of Hask, but only on a subcategory including the types of a particular class. This can't be expressed in Haskell98, in fact it has only become possible quite recently with the advent of constraint kinds. See this example:

instance Functor Set Ranking Ranking where
  fmap = constrainedFmap Set.map

Actually, sets also form a monad in Hask if you use some clever GADT tricks. But this isn't possible for all Foldable containers, hence the standard library doesn't require Functor f => Foldable f.

leftaroundabout
  • 117,950
  • 5
  • 174
  • 319
5

The Functor typeclass doesn’t let you fmap over things that have constraints on the types of their elements. Set requires Ord and StorableVector requires Storable.

It is possible to express a “constrained functor” using GHC’s ConstraintKinds extension, something like:

{-# LANGUAGE ConstraintKinds,
             FunctionalDependencies,
             MultiParamTypeClasses #-}

import GHC.Exts (Constraint)
import Data.Set (Set)
import qualified Data.Set as Set

class ConstrainedFunctor c f | f -> c where
  cfmap :: (c a, c b) => (a -> b) -> f a -> f b

instance ConstrainedFunctor Ord Set where
  cfmap = Set.map

But this machinery wasn’t around when Functor first appeared.

In addition, Functor is supposed to be “shape-preserving”, but e.g. mapping over a Set may change its size.

Jon Purdy
  • 53,300
  • 8
  • 96
  • 166
0

Traverse is a generalisation of map. Traverse can also express foldMap (& so foldLeft/foldRight). So Traverse is both a Functor and a Foldable:

https://www.slideshare.net/pjschwarz/sequence-and-traverse-part-3

Philip Schwarz
  • 69
  • 4