Applicative without a functor

Question

I have a type Image which is basically an c-array of floats. It is easy to create functions such as map :: (Float -> Float) -> Image -> Image, or zipWith :: (Float -> Float -> Float) -> Image -> Image -> Image.

However, I have a feeling that it would also be possible to provide something that looks like an applicative instance on top of these functions, allowing more flexible pixel level manipulations like ((+) <$> image1 <*> image2) or ((\x y z -> (x+y)/z) <$> i1 <*> i2 <*> i3). However, the naive approach fails, since Image type cannot contain things other than floats, making it impossible to implement fmap as such.

How could this be implemented?

Answer 1

Reading the comments, I'm a little worried that size is under the carpet here. Is there a sensible behaviour when sizes mismatch?

Meanwhile, there may be something you can sensibly do along the following lines. Even if your arrays aren't easy to make polymorphic, you can make an Applicative instance like this.

data ArrayLike x = MkAL {sizeOf :: Int, eltOf :: Int -> x}

instance Applicative ArrayLike where
  pure x                 = MkAL maxBound  (pure x)
  MkAL i f <*> MkAL j g  = MkAL (min i j) (f <*> g)

(Enthusiasts will note that I've taken the product of the (Int ->) applicative with that induced by the (maxBound, min) monoid.)

Could you make a clean correspondence

imAL :: Image -> ArrayLike Float
alIm :: ArrayLike Float -> Image

by projection and tabulation? If so, you can write code like this.

alIm $ (f <$> imAL a1 <*> ... <*> imAL an)

Moreover, if you then want to wrap that pattern up as an overloaded operator,

imapp :: (Float -> ... -> Float) -> (Image -> ... -> Image)

it's a standard exercise in typeclass programming! (Ask if you need more of a hint.)

The crucial point, though, is that the wrapping strategy means you don't need to monkey with your array structures in order to put functional superstructure on top.

Answer 2

How would you expect to perform operations on pixels in an image? That is, for ((+) <$> image1 <*> image2), would you want to perform all the operations in Haskell and construct a new resulting image, or would you have to call C functions to do all the processing?

If it's the former, pigworker's answer is the approach I would take.

If instead it's required that all image manipulations be handled via C, how about creating a small DSL to represent the operations?

Answer 3

You'll get a much more compositional Image type if you generalize the "pixel" type from Float and extend from finite & discrete domain (arrays) to infinite & continuous domain. As a demonstration of these generalizations, see the paper Functional Images and a corresponding gallery of (finite samplings of) example images. As a result, you get instances of Monoid, Functor, Applicative, Monad, and Comonad. Moreover, the meanings of these instances are entirely determined by the corresponding instances for functions, satisfying the principle of semantic type class morphisms, as described in the paper Denotational design with type class morphisms. Section 13.2 of that paper briefly describes imagery.