From oleg@pobox.com Wed Apr 11 19:17:45 2001
Date-Sent: Wed, 11 Apr 2001 19:17:44 -0700 (PDT)
Date: Thu, 12 Apr 2001 02:14:27 +0000 (UTC) 
From: oleg@pobox.com
Newsgroups: comp.lang.functional 
Message-Id: <200104120217.TAA03613@adric.cs.nps.navy.mil>
To: comp.lang.functional@mailgate.org
Subject: Re: On products and max3
References: <dspbsqafvym.fsf@sirppi.helsinki.fi>
Reply-to: oleg@pobox.com
Status: OR


> But Haskell doesn't automatically extend these for functions, at least
> I cannot see how to do so (without elements). So you cannot write
> (say)
>   max3 :: a -> a -> a -> a
>   max3 = max . (Pair (max) (id)),

But you can do

prod x y = \(argx,argy) -> ((x argx),(y argy))
max2 x y = if x < y then y else x

max3:: Ord a => a->a->a->a
max3 = (curry (curry ((uncurry max2) .  ((uncurry max2) `prod` id))))
max3 "Bush" "Clinton" "Roosevelt" --=> "Roosevelt"

Placing the right number of 'curry' at the end (at the beginning, to
be precise) quickly becomes unwieldy and cumbersome. Alas, it does not
appear that this process can be automated. (Multi)parameter classes
create more problems in this particular case.

Still it's desirable to let the Haskell system itself flatten the
complex tuple argument into something flatter. For example,

max31:: Ord a => [a]->a
max31 = flatten ((uncurry2 max2) `comp`  ((uncurry2 max2) `prodt` idt))

This corresponds to the categorical notation
	max3 = max . (max * id) 

We can easily take the other branch of the commutative diagram
	max3 = max . (id * max) 
and write

max32:: Ord a => [a]->a
max32 = flatten ((uncurry2 max2) `comp`  (idt `prodt` (uncurry2 max2)))

We can easily verify that max31 and max32 give identical results
max32 [3.14, 2.78, 0.301] ---> 3.14

We generalize the above process to

max41:: Ord a => [a]->a
max41 = flatten
    ((uncurry2 max2) `comp` ((uncurry2 max2) `prodt` (uncurry2 max2)))

which corresponds to
	max4 = max . (max2 * max2)
and

max42:: Ord a => [a]->a
max42 = flatten
    ((uncurry2 max2) `comp` (idt `prodt` (uncurry3l max31)))

which corresponds to
	max4 = max . (id * max3)
max41 ['c','#','a','h'] ---> 'h'


Now to the ugly part. To make the above compositions work flawlessly,
some dirty work has to occur behind the scenes:

data Sig a b = N1 (a->a) | N11 ((a,a)->b) | N11_1 (((a,a),a)->b)
	| N1_11 ((a,(a,a))->b)
	| N1_1_11 ((a,(a,(a,a)))->b)
	| N1_11_1 ((a,((a,a),a))->b)
	| N11_11 (((a,a),(a,a))->b)
	| N11_11_1 (((a,a),((a,a),a))->b)
      
idt = N1 id
uncurry2 f = N11 (\(x,y) -> f x y)
uncurry3l f = N11_1 (\((x,y),z) -> f [x,y,z])

prodt (N1 f) (N11 g) = N1_11 (\(argx,argy) -> ((f argx),(g argy)))
prodt (N1 f) (N11_1 g) = N1_11_1 (\(argx,argy) -> ((f argx),(g argy)))
prodt (N11 f) (N1 g) = N11_1 (\(argx,argy) -> ((f argx),(g argy)))
prodt (N11 f) (N11 g) = N11_11 (\(argx,argy) -> ((f argx),(g argy)))
prodt (N11 f) (N11_1 g) = N11_11_1 (\(argx,argy) -> ((f argx),(g argy)))

comp (N11 g) (N1_11 f) = N1_11 (\x->g(f x))
comp (N11 g) (N11_1 f) = N11_1 (\x->g(f x))
comp (N11 g) (N11_11 f) = N11_11 (\x->g(f x))
comp (N11 g) (N1_11_1 f) = N1_11_1 (\x->g(f x))
comp (N11 g) (N11_11_1 f) = N11_11_1 (\x->g(f x))

flatten (N1 f) [x] = f x
flatten (N11 f) [x,y] = f (x,y)
flatten (N11_1 f) [x,y,z] = f ((x,y),z)
flatten (N1_11 f) [x,y,z] = f (x,(y,z))
flatten (N11_11 f) [x,y,z,u] = f ((x,y),(z,u))
flatten (N11_11 f) [x,y,z,u] = f ((x,y),(z,u))
flatten (N1_11_1 f) [x,y,z,u] = f (x,((y,z),u))


In effect, we do our own light-weight type inference, in parallel to
the compiler's. BTW, I noticed the type errors in this system are
slighly more comprehensible.