[Haskell-cafe] Is it possible to represent such polymorphism?

oleg at okmij.org oleg at okmij.org
Tue Oct 4 11:17:26 CEST 2011


sdiyazg at sjtu.edu.cn wrote:

> >> generalizedFilterMap (\[x,y,z]-> if(x==1&&z==1)then [y*10] else  
> >> [0]) (3,1) [1,2,3,4,1,2,1,3,1,4,1,5,2]
> [0,0,0,0,20,0,30,0,40,0,0]
>
> Of course, I could have simply used [Int] , (Num a)=>[a] or
> (Int,Int,Int), but I'm trying to write code as generic as possible.

As I understand, the point of generalizedFilterMap is to permit the
filter function to examine several elements of the list within the
current window (rather than just the current element). The step argument
determines the step of sliding the window. Further, you wish to make
the step argument default (setting it to 1 if not given).

First of all, if you are interested in stencil computations, there are
several good packages and even the whole DSLs:

  http://research.microsoft.com/en-us/um/people/simonpj/papers/ndp/index.htm
  http://arxiv.org/abs/1109.0777
  http://people.csail.mit.edu/yuantang/

Second, the given code is not as generic as possible. In the above
example, the filter function examines values within the window of size
3. That fact has to be specified twice: in the pattern \ [x,y,z] -> ...
and as the number 3. Having to specify the same information twice is
always less than satisfactory: if we expand the pattern to
\ [x,y,z,u] -> we have to remember to update the other argument to the
function.

There are many solutions to the problem, involving as much type
hacking as one may wish (some of the stencil packages above do track
the size of the stencil statically, in types). Perhaps one of the simplest
solution is the following


> generalizedFilterMap3 :: Int -> ([a]->[a]) -> [a] -> [a]
> generalizedFilterMap3 step f = concatMap f . decimate step . tails
>
> -- pick every n-th
> decimate :: Int -> [a] -> [a]
> decimate 1 lst = lst
> decimate _ [] = []
> decimate n lst = head lst : decimate n (drop n lst)
>
> test1 = generalizedFilterMap3 1 f [1,2,3,4,1,2,1,3,1,4,1,5,2]
>  where
>  f (x:y:z:_) = if x==1&&z==1 then [y*10] else [0]
>  f _         = []

Again there are many, many approaches to default arguments. Perhaps
the simplest, involving no typeclasses and no type computation is the
following

> data GMapArgs a = GMapDflt{step  :: Int,
> 			     gmapf :: [a] -> [a]}
>
> dflt = GMapDflt{step = 1, gmapf = id}
>
> generalizedFilterMap dflt = generalizedFilterMap3 (step dflt) (gmapf dflt)
>
> test2 = generalizedFilterMap dflt{gmapf=f} [1,2,3,4,1,2,1,3,1,4,1,5,2]
>  where
>  f (x:y:z:_) = if x==1&&z==1 then [y*10] else [0]
>  f _         = []
>
> test3 = generalizedFilterMap dflt{gmapf=f,step=2} [1,2,3,4,1,2,1,3,1,4,1,5,2]
>  where
>  f (x:y:z:_) = if x==1&&z==1 then [y*10] else [0]
>  f _         = []

It requires no extensions. Record puns and other Record extensions
make the approach nicer.


> What I want is some thing like this in C++:
>
> float f(char x){ return 0.1f; }
> int f(double x){ return 1; }

One should point out the difficulties of comparing C++ with
Haskell. Haskell is designed to be higher-order, making it simple to
pass functions as arguments to other functions. Your code for generic
maps relies on that behavior. Try passing the overloaded C++ function
'f' defined above to some other function. That is, implement something
like the following
	float g(??? f) { return f('x') + f(1.0); }
	int main(void) {printf("%g",g(f)); return 0;}

One can certainly implement the above outline in C++, but it won't be
simple.




More information about the Haskell-Cafe mailing list