CODEWITHSUNDEEP
haskell
levy
levy

Reputation: 53

Haskell quiz: a simple function

I'm not a Haskell programmer, but I'm curious about the following questions.

Informal function specification:

Let MapProduct be a function that takes a function called F and multiple lists. It returns a list containing the results of calling F with one argument from each list in each possible combination.

Example:

Call MapProduct with F being a function that simply returns a list of its arguments, and two lists. One of the lists contains the integers 1 and 2, the other one contains the strings "a" and "b". It should return a list that contains the lists: 1 and "a", 1 and "b", 2 and "a", 2 and "b".

Questions:

Upvotes: 2

Views: 1287

Answers (3)

MtnViewMark
MtnViewMark

Reputation: 5140

It is possible to define a function mapProduct that works for any arity of function:

{-# LANGUAGE FlexibleInstances, TypeFamilies #-}

module MapProduct (
    mapProduct
    ) where

import Control.Monad

newtype ProdFuncList a b = ProdFuncList [ a -> b ]


class MapProdResult p where
    type MapProdArg p
    apNext :: ProdFuncList x (MapProdArg p) -> [x] -> p

instance (MapProdResult b) => MapProdResult ([a] -> b) where
    type MapProdArg ([a] -> b) = (a -> MapProdArg b)
    apNext (ProdFuncList fs) = apNext . ProdFuncList . ap fs

instance MapProdResult [b] where
    type MapProdArg [b] = b
    apNext (ProdFuncList fs) = ap fs


mapProduct :: (MapProdResult q) => (a -> MapProdArg q) -> [a] -> q
mapProduct f = apNext (ProdFuncList [f])

Here it is in action:

> :l MapProduct.hs 
[1 of 1] Compiling MapProduct       ( MapProduct.hs, interpreted )
Ok, modules loaded: MapProduct.
> mapProduct (+10) [1..4] :: [Int]
[11,12,13,14]
> mapProduct (*) [1..4] [10..12] :: [Int]
[10,11,12,20,22,24,30,33,36,40,44,48]
> mapProduct (\a b c -> a:b:c:[]) "bcs" "ao" "dnt" :: [String]
["bad","ban","bat","bod","bon","bot","cad","can","cat","cod","con","cot","sad","san","sat","sod","son","sot"]

The downside of this approach is that you'll most likely have to type annotate the result (as shown in the examples above). It would be much more idiomatic to simply use fmap and ap directly:

> :m + Control.Monad
> (+10) `fmap` [1..4]
[11,12,13,14]
> (*) `fmap` [1..4] `ap` [10..12]
[10,11,12,20,22,24,30,33,36,40,44,48]
> (\a b c -> a:b:c:[]) `fmap` "bcs" `ap` "ao" `ap` "dnt"
["bad","ban","bat","bod","bon","bot","cad","can","cat","cod","con","cot","sad","san","sat","sod","son","sot"]

This requires no type annotations, and is fully general over all monads, not just [].

(The MapProduct module above could easily be generalized over all monads as well. I didn't so as to make it clearly solve the original question.)

Upvotes: 2

kennytm
kennytm

Reputation: 523284

  • How is MapProduct implemented?

.

Prelude> :m + Control.Applicative
Prelude Control.Applicative> (,,) <$> [1,2,3] <*> ["a","b","c"] <*> [0.8, 1.2, 4.4]
[(1,"a",0.8),(1,"a",1.2),...,(3,"c",4.4)]
  • What is the function's type? What is F's type?

The type of F depends on the list you want to apply. <$> here is fmap, and (<*>) :: f(a->b) -> f a -> f b where f = [] here.

  • Can you handle inhomogeneous lists as input? (e.g. 1 and "a" in one of the input lists)

There is no such thing as an heterogeneous list. But you can simulate a heterogeneous list for a specific context with existential types. And then you can just use the method above to do the MapProduct.

*Main Control.Applicative> :i SB
data ShowBox where
  SB :: forall s. (Show s) => s -> ShowBox
    -- Defined at v.hs:1:35-36
*Main Control.Applicative> [SB 2, SB "a", SB 6.4]
[2,"a",6.4]
*Main Control.Applicative> (,) <$> [SB 2, SB "a", SB 6.4] <*> [SB 'z', SB 44]
[(2,'z'),(2,44),("a",'z'),("a",44),(6.4,'z'),(6.4,44)]

Upvotes: 8

sepp2k
sepp2k

Reputation: 370142

The function that you describe is closely related to the zipWithN functions. It will have the same type - it will just result in bigger result lists. Now the problem is that there is no way to express "a function that takes N arguments of the types t_1, ..., t_n" or "n lists of the types [t_1],...,[t_n]" (or "an n-tuple of type ([t_1], ..., [t_n]") ) in haskell's type system (without extensions like template haskell). This is why there is not one zipWith function, but one for each number of arguments lists that is supported.

So to answer your questions:

  • It is implemented by defining a function mapProductN for every number N that you want to support. For N=2 it would look like this:

    mapProduct f l1 l2 = [f x1 x2 | x1 <- l1, x2 <- x2]

    Or as a general blueprint (i.e. pseudo-code) how to define the functions for any N:

    mapProduct f l1 ... ln = [f x1 ... xn | x1 <- l1, ..., xn <- ln]

  • As I said it's the same as the types of the zipWith functions, i.e.:

    zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]  
zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]  
zipWith4 :: (a -> b -> c -> d -> e) -> [a] -> [b] -> [c] -> [d] -> [e]

    Since f is the first argument to the function, the type of the first argument is f's type (so for n=2 it'd be a -> b -> c)

  • Well since it has the same type as zipWith and zipWith does something else, that'd be a no.

  • Haskell doesn't allow inhomogeneous lists without an extension.

  • There's an upper limit on the number of lists unless you're willing to spend the time writing infinite versions of mapProduct.

Upvotes: 1

Related Questions