Haskell: Making a function to act on list

Question

Possible Duplicate:
Why is such a function definition not allowed in haskell?

I would like to create a function flist that takes a function f as argument and returns another function whose argument will be a list but behaves exactly same as f.

For example:

let f x1 x2 x3 = x1+ x2 + x3

I want this behaviour

(flist f) [x1,x2,x3] = x1+x2+x3

When the list is not of length 3 it may behave in any way. flist should take care of any function (not only functions with 3 argument, i.e. if g x1 x2 x3 x4 = x1+x2+x3*x4, then (flist g) [x1,x2,x3,x4] = x1+x2+x3*x4 ).

I tried this,

flist f [] = f
flist f (x:xs) = flist (f x) xs

But it is not working. How do I achieve this? Can I use data types to do this?

Answer 1

With type families, you can get pretty far—but it surely is not for the faint of heart:

{-# LANGUAGE FlexibleContexts  #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE TypeFamilies      #-}

class FList a where
  type Point a
  flist :: a -> [Point a] -> Point a

instance FList (a -> a) where
  type Point (a -> a) = a
  flist f [x] = f x

instance (FList (a -> b), a ~ Point (a -> b)) => FList (a -> (a -> b)) where
  type Point (a -> (a -> b)) = Point (a -> b)
  flist f (x : xs) = flist (f x) xs

For your example, we get:

> let f x y z = x + y + z
> flist f [2, 3, 5]
10

Answer 2

You can't create your flist directly, because there's no sensible type to give it.

flist :: (a -> a -> a -> ..... -> a) -> [a] -> a

depending on how long the list is - you only know the type of flist once you know how long the list is, i.e. not at compile time, so you can't compile it.

It is possible with Template Haskell to write an flist "function" that you could use like [flist| (+) [3,4] ] but Template Haskell is very advanced stuff that I think you should avoid just now, and the syntax is even uglier than the one you wanted, which was already uglier than (+) 3 4.

If you know how many arguments you will have you can use one of the following functions:

flist1 f [x] = f x
flist2 f [x,y] = f x y
flist3 f [x,y,z] = f x y z
flist4 f [a,b,c,d] = f a b c d
flist5 f [a,b,c,d,e] = f a b c d e

but if you're wanting to do something uniform with them, like add them up, you can use a pre-written higher-oder function like sum or product to add or multiply, or roll your own using foldl. (For example, the language definition of sum is sum = foldl (+) 0.

Answer 3

This isn't too hard for a fixed number of arguments, e.g.

flist3 f [a,b,c] = f a b c
flist3 _ _       = 0

(I notice that you are using the function in a numeric context, so defaulting to 0 is perfectly fine.)

In a more general context, one can represent success- or failure-to-match by returning a Maybe value, e.g.

flist3 f [a,b,c] = Just $ f a b c
flist3 _ _       = Nothing

This can then be used like:

import Data.Maybe

exp f n = (sum . mapMaybe (flist3 f) $ booleanCube n) / 2^n

(mapMaybe maps a function a -> Maybe b over a list, but drops the Nothings and collects the Just values into a list. If dropping the Nothings isn't the desired behaviour, then one can use mapM instead (with a few adjustments to the function).)

However, if exp is supposed to be able to take functions of type a -> a -> a and a -> a -> a -> a etc, then giving exp a usable type signature will be hard (probably impossible in a non-dependently typed language like Haskell), since the arity of f isn't fixed.

(As @Mystic demonstrates, it is possible to create variadic functions in Haskell using type-classes, but that has slightly different behaviour to what you desired.)

Answer 4

flist f [] = f
flist f (x:xs) = flist (f x) xs

Something like this will not work because you the type of f is not fixed.

f :: (? -> b) -> [a] -> b 

What do you insert at ? will depend on number of elements in the list.
Well something like type classes can be used to define such functions.

One way is to explicitly define each function for all the types of function you have or you can use little type hackery.

I wrote a messy hack, just to show that it is possible using some type trickery. It is still not very flexible as you will need to provide types of all the arguments explicitly. Adding some functional dependencies might solve that. It raises an exception when number of elements does not match the order of function f.

{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}

class FList a b c where 
    flist :: a -> b -> c

instance FList a [s] a where 
    flist x _ = x


instance (FList a [s] b) => FList (s -> a) [s] b where 
    flist f (x:xs) =  flist (f x) xs


f:: Int -> Int -> Int -> Int 
f a b c = a + b * c

test :: [Int]
test = [1,2,3]

foo :: Int 
foo = (flist f) test  

Whatever you are trying to do will probably not need such kind of functions. My only advice would be to revisit your code and try to see if something simple fits.

Answer 5

There are many papers on arity-generic programming e.g.

http://www.seas.upenn.edu/~ccasin/papers/aritygen.pdf

But you should explain a larger task at hand because it seems like advanced generic techniques are not necessary and it's possible to work your problem around.