Home » forums » LtU Forum

Deriving Functions to Work on Different Types of Data

In Mathematics one often writes f(X) instead of {f(x) | x in X} where X is a set. Array languages like J allow you to write a+b for elementwise addition of arrays. Mathematicians also write f+g = lambda x -> f(x) + g(x) for pointwise addition of functions. Other examples are using functions on symbolic data or on time varying values (like in FRP).

Do you have ideas on how to use this notation in programming languages? Are there languages that allow you to do this in a general way? (i.e. without defining every operator +, *, /, etc. to work on different types of data seperately) Can this work in both statically and dynamically typed languages? How can you handle cases like a + f where a and f aren't of the same type, for example a is a time-varying value and b is a function?

Another example:

I'd expect A+B where A and B are sets to produce {a+b | a in A, b in B}. What should A+f do?

1) {lambda x -> a+x | a in A}, a set of functions
2) lambda x -> {a+x | a in A}, a function that returns sets
3) Error.

Maybe it's possible to determine what to do from the context.

Thank you for your ideas.

By Jules Jacobs at 2009-05-23 21:53 | LtU Forum | previous forum topic | next forum topic | other blogs | 6019 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Two things you should check

Two things you should check out, Object Oriented Programming (A good book on this would be Bruce Eckels stuff online or Art of Metaobject Protocol) and also Haskells Typeclass dispatch mechanism (which is working in a statically typed context).

You probably notice that people doing these kind of notational puns is rare in programming (Other than the APLalikes). I would supposed the reason is that one of the main things we like to in programming is make things as explicit and unambiguous as possible.

By Alex1 at Sat, 2009-05-23 22:39 | login or register to post comments

"As explicit and unambiguous as possible"?

So why was it that Bliss never caught on, where A always meant a pointer, and assignment was written A = .B, and + always meant integer addition, and you had to write something else for floating-point addition?

Artful inexplicitness (I don't say unambiguity) is often a Good Thing.

By johnwcowan at Sat, 2009-05-23 23:04 | login or register to post comments

OCAML + and +.

Actually I think it is safe to say that OCAML caught on, and there + is for integers and +. for floats. Ditto for the other machine arithmetic operators.

That unambiguity helps alot when reading code.

Otherwise I would agree, except I'd say "sometimes" rather than "often".

By dennisdjensen at Sun, 2009-05-24 15:50 | login or register to post comments

Pure

You can do some of this in Pure (a dynamically typed FPL based on term rewriting):

> f+g = \x -> f x + g x;
> f x = 3*x; g x = x/2;
> (f+g) 9;
31.5

There's no way you can write a generic rule in Pure that automatically lifts every function to aggregates, I'm afraid. But if it's too much of a hassle to write map h xs, you can simply add a rule like this (taking matrices as an example):

> h x::int = 2*x;
> h x::matrix = map h x;
> h {1,2,3,4};
{2,4,6,8}

All dispatching is done dynamically, so it's easy to add more rules like these, which extend a given function (even builtins) to any kind of data you want.

By Albert Graef at Sun, 2009-05-24 20:10 | login or register to post comments

Interesting. Pure is

Interesting. Pure is definitely something I have to explore. How does pure know that f and g are functions in your definition of +? Why does 2+3 still work?

I suppose you can write an explicit lifting function in Pure (like in Haskell):

lift2 op xs::collection ys::collection = zipWith op xs ys
lift2 op X::set Y::set = map (\(x,y) -> op x y) (cartesianProduct X Y)

it doesn't look very good: lift2 (+) xs ys vs. xs + ys. Another problem with this approach is that this doesn't extend existing functions that use +, like sum. I.e. you can't do sum [f,g,h].

And the problem of how to handle lift2 (+) xs::collection Y::set remains.

By Jules Jacobs at Sun, 2009-05-24 22:11 | login or register to post comments

How does pure know that f


How does pure know that f and g are functions in your definition of +?

It doesn't. f and g are just untyped variables here. Actually, the definition I gave is a bit silly. In production code, you'd probably want to use something less polymorphic, like this:


f+g = \x -> f x + g x if arity f>0 && arity g>0;


Why does 2+3 still work?

Pure does priority rewriting, i.e., equations are considered in the order in which they are written. Integer addition is defined in the prelude, so it takes priority over the definition above.

By Albert Graef at Tue, 2009-05-26 22:55 | login or register to post comments

Check out Haskell's applicative functors


> let f x = 3 * x
> let g x = x / 2
> liftA2 (+) f g 9
31.5
> liftA2 (+) [1,2] [10,20]
[11,21,12,22]

To combine lifting over lists and lifting over functions, we need to lift (+) two times, and use pure to lift the arguments.

> let fns = liftA2 (liftA2 (+)) [pure 1, pure 2] (pure f)
> map ($ 10) fns
[31,32]

By Sjoerd Visscher at Sun, 2009-05-31 10:45 | login or register to post comments