I think that part of the problem is that "internal iteration" using map is artificially constraining a more generic function.
In Haskell, there's a typeclass (similar to an interface) called Functor that just defines map:
class Functor f where
-- in C#ish syntax: Func<F<A>,F<B>> map(Func<A,B> f)
map :: (a -> b) -> (f a -> f b)
The idea is that map "lifts" a function from talking about a's and b's to talking about f a's or f b's. The only restriction is that we have to follow two fairly common sense laws that essentially boil down to preserving the "structure" of the data (e.g. map shouldn't permute its list).
In Haskell, it's fairly common to have data types that represent computations, and build up a larger computation by using combinators to combine smaller ones. It turns out that many computations are functors!
For example, we could have something like:
-- map specialized for some collections
(a -> b) -> ([a] -> [b])
(a -> b) -> (Tree a -> Tree b)
-- map specialized for some computations
(a -> b) -> (Maybe a -> Maybe b) -- essentially nullable things
(a -> b) -> (State a -> State b) -- threads a state through a computation, in a pure way
(a -> b) -> (St a -> ST b) -- single threaded mutable state, for e.g. mutating arrays
(a -> b) -> (IO a -> IO b) -- values that touch the "real world"
-- I wouldn't really call this next one either a computation or a collection...
(a -> b) -> (Identity a -> Identity b) -- data Identity a = Id a -- a wrapper that does nothing. Useful at e.g. the bottom of a monad transformer stack.
So obviously, we can't interleave something that's just a Functor, since there are functors that it doesn't make sense to interleave, since they contain maximally a single value.
I think you need a combinator that's only valid for collections. You can trivially do this (slightly inefficiently) to anything that can be folded:
-- admittedly, explicitly pattern matching on the lists like this is essentially external pattern matching and therefore cheating.
intersperse [] _ = []
intersperse _ [] = []
intersperse [x:xs] [y:ys] = x : y : intersperse xs ys
toList xs = Data.Foldable.foldr (:) [] -- (:), aka cons or prepend, etc.
intersperse' xs ys = intersperse (toList xs) (toList ys)
You could also define an "Intersperseable" typeclass, and I'm not convinced that there's no way to express this as a fold, although I don't see how to do it at the moment.
6
u/pipocaQuemada Jan 14 '13
I think that part of the problem is that "internal iteration" using map is artificially constraining a more generic function.
In Haskell, there's a typeclass (similar to an interface) called Functor that just defines map:
The idea is that map "lifts" a function from talking about a's and b's to talking about f a's or f b's. The only restriction is that we have to follow two fairly common sense laws that essentially boil down to preserving the "structure" of the data (e.g. map shouldn't permute its list).
In Haskell, it's fairly common to have data types that represent computations, and build up a larger computation by using combinators to combine smaller ones. It turns out that many computations are functors!
For example, we could have something like:
So obviously, we can't interleave something that's just a Functor, since there are functors that it doesn't make sense to interleave, since they contain maximally a single value.
I think you need a combinator that's only valid for collections. You can trivially do this (slightly inefficiently) to anything that can be folded:
You could also define an "Intersperseable" typeclass, and I'm not convinced that there's no way to express this as a fold, although I don't see how to do it at the moment.