I've tried to understand Haskell's traverse
function and to implement it in Javascript, but I'm stuck. When I look at its type (Functor t, Foldable t, Applicative f) => (a -> f b) -> t a -> f (t b)
, I understandd that I need <$>
(map
in JS), <*>
(ap
in JS) and fold
in order to implement it.
I came up with the following code:
// Church encoded Identity newtype
const Ident = x => f => f(x);
const traverse = map => ft => tx => map(y => Ident(y)) (tx(x => ft(x)));
// list functor
map = f => xs => xs.map(f);
// helper
I = x => x;
// data
idA = Ident(1);
idB = Ident(null);
// and run
const r1 = traverse(map) (x => x === null ? [] : [x]) (idA); // [Ident(1)]
const r2 = traverse(map) (x => x === null ? [] : [x]) (idB); // []
console.log(r1 [0] (I)); // 1
console.log(r2); // []
Since I used Ident
and Array
the type simplifies to (a -> [b]) -> Ident a -> [Ident b]
. traverse
runs the effect when it rebuilds the data structure. If I am not mistaken one can observe the non-deterministic effect of the list functor in my example.
But where is the applicative? And why does the traversable have to be a functor? Is it just a coincidence that I didn't need them for my sketch?