Latest update Jan 3, 2003

A Closer Look at Lifting

The Xarray library provides a number of modules to facilitate the lifting of operations to constructed types, and to provide convenient, lifted standard operations on arrays: Liftable, LiftArray, LiftMaybe, LiftBool, LiftEq, LiftOrd, LiftNum, LiftArrayNum, and LiftMaybeNum. The intended use is for convenient spreadsheet array programming, but the modules provide general declarations that can be used in many other contexts.

Liftable is a constructor class that defines operations to lift constants and functions to constructed data types. It can be seen as an extension to Functor. Liftable k declares the following functions:

• lift0 :: a -> k a, lifts a constant of type a into a value of type k a.
• lift1 :: (a -> b) -> (k a -> k b), lifts a function in one argument, of type (a -> b), into a function of type (k a -> k b). lift1 is essentally fmap.
• lift2 :: (a -> b -> c) -> (k a -> k b -> k c), lifts a function in two arguments, of type (a -> b -> c), into a function of type (k a -> k b -> k c).

We currently provide two pre-declared instances of Liftable: Array a (extended arrays), in module LiftArray and Maybe, in module LiftMaybe. The instance declaration for Maybe is straightforward, and the lifting functions act as if the lifted functions are being lifted into strict and total functions over a cpo where Nothing represents bottom. The lifting functions for Array a apply the lifted function elementwise to the array arguments. They are based on a similar view, where arrays are seen as partial functions from indices and lifting is a kind of function composition. This means that lift1 f a should have the same bound as a (f (a!i) is defined precisely when a!i is), and that the bound of lift2 f a b should be the intersection of the bounds of a and b (f (a!i) (b!i) is defined precisely when a!i and b!i are).

The LiftNum module declares k a to be an instance of Num, Floating, and Fractional when k belongs to Liftable (given suitable constraints on a). This does not work in plain Haskell 98, where instance declarations must be for types with an outermost constant constructor, but is handled by hugs -98 +o. To stay Haskell 98-compatible, one instance declaration for each numeric type must be provided for each instance of Liftable. The modules LiftArrayNum and LiftMaybeNum provide such declarations for Array a and Maybe, respectively.

These instance declarations make it possible to use numerical operations directly on arrays, with an intuitive semantics: for instance, we can write sin a + b/5 to create an array whose i'th element is sin (a!i) + b!i/5. This style of array programming is much appreciated in numerical computing, and supported by HPC-oriented array languages. Numerical constants are mapped into infinite arrays by fromInteger and fromRational. Bounds of infinite arrays represent the universal set, and the "bounds intersection semantics" of lifted binary operations ensures that the result of, say, b/5 will have the same bounds as b. With the numerical instance declarations for Maybe, the operations are also lifted to arrays whose elements belong to the proper numerical Maybe type, in a natural way. This is useful when arrays are used for spreadsheet calculations, since spreadsheet tables might be sparse and their "holes" then can be represented by Nothing.

LiftBool, LiftEq, and LiftOrd define lifted boolean and relational operators: &&*, ||*, not', ==*, /=*, <*, >*, <=*, >=*. The boolean operators are already defined over a single type, and the type signatures for the Eq and Ord operations prohibit overloading the operator names for the lifted operations, so a "*" is appended to the operator names (except for not). (This follows the naming convention in Paul Hudak's The Haskell School of Expression: Learning Functional Programming through Multimedia, where operations are lifted over behaviors.)