Difference between revisions of "APL"
Jump to navigation
Jump to search
(New page: = An APL library for Haskell = APL is an array language with a highly-functional flavour, and a rich set of carefully-thought-out array operations. It would be interesting to build a Has...) |
|||
(2 intermediate revisions by one other user not shown) | |||
Line 4: | Line 4: | ||
This page collects thoughts loosely based around that idea. |
This page collects thoughts loosely based around that idea. |
||
+ | |||
+ | = APL arrays in Haskell = |
||
+ | |||
+ | <hask> |
||
+ | data Array elt -- Forces uniform element types |
||
+ | </hask> |
||
+ | |||
+ | * Need rank-zero arrays |
||
+ | |||
+ | * In a rank-3 arrary, any of the axes can have zero length |
||
+ | <tt> |
||
+ | e.g. (3 x 0 x 4) array /= (0 x 0 x 4) array |
||
+ | </tt> |
||
+ | |||
+ | * Prototypical item? Leave open for now. A minefield. |
||
+ | |||
+ | Major question: should the rank be visible in the type at all? |
||
+ | <tt> |
||
+ | Plan A: data Array elt |
||
+ | </tt> |
||
+ | <tt> |
||
+ | Plan (Succ A): data Array rank elt |
||
+ | </tt> |
||
+ | |||
+ | = The main API, using Plan A = |
||
+ | |||
+ | <haskell> |
||
+ | data Array a -- Rectangular! |
||
+ | |||
+ | type Scalar a = Array a -- Rank 0, length 1 |
||
+ | type Vector a = Array a -- Rank 1! |
||
+ | type Matrix a = Array a -- Rank 2! |
||
+ | type Axis = Nat |
||
+ | |||
+ | -- Arrays can be added, multiplied, etc |
||
+ | class Num a where |
||
+ | (+) :: Num a => a -> a -> |
||
+ | |||
+ | instance Num a => Num (Array a) where .. |
||
+ | |||
+ | -- All indexing is 0-based (Dijkstra) |
||
+ | </haskell> |
||
+ | |||
+ | Basic operations |
||
+ | <haskell> |
||
+ | -- A rank-0 array contains one item |
||
+ | zilde :: Vector a -- Empty vector, rank 1 |
||
+ | enclose :: a -> Scalar a -- Returns a rank 0 array, of |
||
+ | -- depth one greater than input |
||
+ | |||
+ | encloseA :: Nat -- r |
||
+ | -> Array a -- Rank n |
||
+ | -> Array (Array a) -- Outer rank r, inner rank n-r |
||
+ | -- encloseA 2 (Array [3,1,4]) : Array [3] (Array [1,4]) |
||
+ | -- enclose a = encloseA 0 (when a is an array) |
||
+ | |||
+ | disclose :: Scalar a -> Array a |
||
+ | discloseA :: Array (Array a) -> Array a |
||
+ | |||
+ | iota :: Nat -> Array Nat -- iota n = [0 1 2 3 ... n-1] |
||
+ | |||
+ | ravel :: Array a -> Vector a -- Flattens an array of arbitrary rank |
||
+ | -- (including zero!) in row-major order |
||
+ | -- Does not change depth |
||
+ | |||
+ | reshape :: Vector Nat -- s: the shape |
||
+ | -> Array a -- Arbitrary shape |
||
+ | -> Array a -- Shape of result = s |
||
+ | -- NB: ravel a = product (shape a) `reshape` a |
||
+ | |||
+ | product :: Num a => a -> Array a -> Array a |
||
+ | productA :: Num a => Axis -> a -> Array a -> Array a |
||
+ | -- Result has rank one smaller than input |
||
+ | |||
+ | shape :: Array a -> Vector Nat |
||
+ | -- shape [[1 3] [5 2] [3 9]] = [3 2] |
||
+ | -- shape [3 2] = [2] |
||
+ | -- shape [2] = [1] |
||
+ | |||
+ | -- rank = shape . shape -- Rank 1 and shape [1] |
||
+ | -- Or we could have rank :: Array a -> Nat |
||
+ | </haskell> |
||
+ | |||
+ | Swapping rank and depth |
||
+ | <haskell> |
||
+ | rankOperator :: |
||
+ | -- This is in J and it is somehow lovely in a way |
||
+ | -- that ordinary mortals cannot understand |
||
+ | -- rankOp 1 (+) A B |
||
+ | |||
+ | -- Swapping rank and depth |
||
+ | -- Array [2,4,5,3] Float |
||
+ | -- --> Array [2,5] (Array [4,3] Float) |
||
+ | -- And the reverse! |
||
+ | |||
+ | rankOp rank-spec f = reshape rank-spec . f . unreshape rank-spec |
||
+ | |||
+ | |||
+ | transpose :: Vector Nat -- Permutation of (iota (rank arg)) |
||
+ | -> Array a -- Arg |
||
+ | -> Array a |
||
+ | -- Permutes the axes |
||
+ | </haskell> |
||
+ | |||
+ | More operations |
||
+ | <haskell> |
||
+ | class Item a wher |
||
+ | depth :: a -> Nat |
||
+ | |||
+ | instance Item Float where |
||
+ | depth _ = 0 |
||
+ | instance Item a => Item (Array a) where |
||
+ | depth _ = 1 + depth (undefined :: a) |
||
+ | |||
+ | |||
+ | catenate :: Array a -> Array a -> Array a |
||
+ | -- Concatenates on last axis (or first in J) |
||
+ | -- Checks for shape compatibility |
||
+ | catenateA :: Axis -> Array a -> Array a -> Array a |
||
+ | -- You can specify the axis |
||
+ | |||
+ | -- Swapping rank with depth |
||
+ | flatten :: Vector (Vector a) -> Array a |
||
+ | |||
+ | vector :: [a] -> Vector a |
||
+ | |||
+ | each :: (a -> b) -> Array a -> Array b |
||
+ | |||
+ | simpleIndex -- m [a;b] |
||
+ | :: Array a -- a: The array to index |
||
+ | -> Vector (Array Nat) -- i: Outer array is a tuple |
||
+ | -- of length = rank a |
||
+ | -> Array a -- shape result = shape i[0] x shape i[1] .... |
||
+ | simpleIndex a is = chooseIndex a (disclose (reduce (outer catenate) zilde is)) |
||
+ | -- We aren't quite sure about this definition |
||
+ | |||
+ | reduce :: (Array a -> Array a -> Array a) -> Array a |
||
+ | -- All rank one smaller than input |
||
+ | -> Array a -- Input |
||
+ | -> Array a -- Rank one smaller than input |
||
+ | -- except that rank 0 input gives identity |
||
+ | |||
+ | reduceA :: Axis -> (a -> a -> a) -> a |
||
+ | -> Array a |
||
+ | -> Array a -- Rank one smaller than ieput |
||
+ | |||
+ | |||
+ | outer :: (a -> b -> c) -- Function argument |
||
+ | -> Array a -> Array b -- Two array arguments, arg1, arg2 |
||
+ | -> Array c -- Shape result = shape arg1 ++ shape arg2 |
||
+ | |||
+ | -- simpleIndex a (vector [enclose 3, enclose 4]) :: Array a (rank 0) |
||
+ | -- mat [3 ; 4] |
||
+ | |||
+ | chooseIndex -- m [b] |
||
+ | :: Array a -- a: The array to index |
||
+ | -> Array (Vector Nat) -- i: Inner arrays are the index tuples |
||
+ | -- of length = rank a |
||
+ | -> Array a -- shape result = shape i |
||
+ | </haskell> |
||
+ | |||
+ | Various monomorphic pick operators |
||
+ | <haskell> |
||
+ | pick1 :: Vector (Matrix (Vector a)) |
||
+ | -> Array (Nat, (Nat,Nat), Nat) |
||
+ | -> Array a |
||
+ | |||
+ | pick2 :: Vector (Matrix a) |
||
+ | -> Array (Nat, (Nat,Nat)) |
||
+ | -> Array a |
||
+ | |||
+ | -- Just an instance of pick2 |
||
+ | pick2 :: Vector (Matrix (Vector a)) |
||
+ | -> Array (Nat, (Nat,Nat)) |
||
+ | -> Array (Vector a) |
||
+ | </haskell> |
||
+ | |||
+ | = Reference implementation = |
||
+ | |||
+ | This implementation of the above API is intended to give its semantics. |
||
+ | It is not intended to run fast! |
||
+ | |||
+ | <haskell> |
||
+ | data Array a = Arr Shape [a] |
||
+ | |||
+ | type Shape = [Nat] |
||
+ | -- Invariant: Arr s xs: product s = length xs |
||
+ | |||
+ | ravel :: Array a -> Vector a |
||
+ | ravel (Arr s a) = Arr [product s] a |
||
+ | |||
+ | zilde :: Vector a -- Empty vector, rank 1 |
||
+ | zilde = Arr [0] [] |
||
+ | |||
+ | enclose :: a -> Scalar a -- Returns a rank 0 array, of |
||
+ | -- depth one greater than input |
||
+ | enclose x = Arr [] [x] |
||
+ | |||
+ | disclose :: Scalar a -> a |
||
+ | disclose (Arr [] [x]) = x |
||
+ | |||
+ | discloseA (Arr outer items) |
||
+ | = Arr (outer ++ inner) [ i | Arr _ is <- items, i <- is ] |
||
+ | where |
||
+ | (Arr inner _ : _) = items |
||
+ | |||
+ | |||
+ | transpose :: Vector Nat -- Permutation of (iota (rank arg)) |
||
+ | -> Array a -- Arg |
||
+ | -> Array a |
||
+ | transpose (Arr [n] perm) (Arr shape items) |
||
+ | = assert (n == length shape ) $ |
||
+ | Arr (permute perm shape) |
||
+ | (scramble ... items) |
||
+ | |||
+ | -- Property: disclose (enclose x) == x |
||
+ | |||
+ | shape :: Array a -> Vector Nat |
||
+ | shape (Arr s a) = Arr [1] s |
||
+ | |||
+ | reshape :: Vector Nat -- s: the shape |
||
+ | -> Array a -- Arbitrary shape |
||
+ | -> Array a -- Shape of result = s |
||
+ | reshape (Arr [n] s) (Arr s' elts) |
||
+ | | null elts = error "Reshape on empty array" |
||
+ | | otherwise |
||
+ | = Arr s (take (product s) (cycle elts)) |
||
+ | |||
+ | each :: (a -> b) -> Array a -> Array b |
||
+ | each f (Arr s xs) = Arr s (map f xs) |
||
+ | |||
+ | reduce :: (Array a -> Array a -> Array a) -> Array a |
||
+ | -- All rank one smaller than input |
||
+ | -> Array a -- Input |
||
+ | -> Array a -- Rank one smaller than input |
||
+ | -- except that rank 0 input gives identity |
||
+ | reduce k z (Arr [] [item]) |
||
+ | = Arr [] [item] -- Identity on rank 0 |
||
+ | reduce k z (Arr (s:ss) items) |
||
+ | = foldr k z (chop ss items) |
||
+ | |||
+ | encloseA :: Nat -> Array a -> Array a |
||
+ | encloseA n (Arr shape items) |
||
+ | = Arr outer_shape (chop inner_shape items) |
||
+ | where |
||
+ | (outer_shape, inner_shape) = splitAt n shape |
||
+ | |||
+ | chop :: Shape -> [item] -> [Array item] |
||
+ | chop s [] = [] |
||
+ | chop s is = Arr s i : chop s is' |
||
+ | where |
||
+ | (i,is') = splitAt (product s) is |
||
+ | </haskell> |
||
+ | |||
+ | == A couple of examples == |
||
+ | |||
+ | <tt> |
||
+ | x = 0 1 2 : Array Float = Arr [2,3] [0,1,2,3,4,5] |
||
+ | 3 4 5 |
||
+ | |||
+ | enclose x :: Array (Array Float) |
||
+ | = Arr [] [Arr [2,3] [0,1,2,3,4,5]] |
||
+ | </tt> |
Latest revision as of 06:36, 29 June 2012
An APL library for Haskell
APL is an array language with a highly-functional flavour, and a rich set of carefully-thought-out array operations. It would be interesting to build a Haskell library that offered a Haskell rendering of APL's array algebra, possibly (though not definitely) bound to a mature implementation.
This page collects thoughts loosely based around that idea.
APL arrays in Haskell
data Array elt -- Forces uniform element types
- Need rank-zero arrays
- In a rank-3 arrary, any of the axes can have zero length
e.g. (3 x 0 x 4) array /= (0 x 0 x 4) array
- Prototypical item? Leave open for now. A minefield.
Major question: should the rank be visible in the type at all? Plan A: data Array elt Plan (Succ A): data Array rank elt
The main API, using Plan A
data Array a -- Rectangular!
type Scalar a = Array a -- Rank 0, length 1
type Vector a = Array a -- Rank 1!
type Matrix a = Array a -- Rank 2!
type Axis = Nat
-- Arrays can be added, multiplied, etc
class Num a where
(+) :: Num a => a -> a ->
instance Num a => Num (Array a) where ..
-- All indexing is 0-based (Dijkstra)
Basic operations
-- A rank-0 array contains one item
zilde :: Vector a -- Empty vector, rank 1
enclose :: a -> Scalar a -- Returns a rank 0 array, of
-- depth one greater than input
encloseA :: Nat -- r
-> Array a -- Rank n
-> Array (Array a) -- Outer rank r, inner rank n-r
-- encloseA 2 (Array [3,1,4]) : Array [3] (Array [1,4])
-- enclose a = encloseA 0 (when a is an array)
disclose :: Scalar a -> Array a
discloseA :: Array (Array a) -> Array a
iota :: Nat -> Array Nat -- iota n = [0 1 2 3 ... n-1]
ravel :: Array a -> Vector a -- Flattens an array of arbitrary rank
-- (including zero!) in row-major order
-- Does not change depth
reshape :: Vector Nat -- s: the shape
-> Array a -- Arbitrary shape
-> Array a -- Shape of result = s
-- NB: ravel a = product (shape a) `reshape` a
product :: Num a => a -> Array a -> Array a
productA :: Num a => Axis -> a -> Array a -> Array a
-- Result has rank one smaller than input
shape :: Array a -> Vector Nat
-- shape [[1 3] [5 2] [3 9]] = [3 2]
-- shape [3 2] = [2]
-- shape [2] = [1]
-- rank = shape . shape -- Rank 1 and shape [1]
-- Or we could have rank :: Array a -> Nat
Swapping rank and depth
rankOperator ::
-- This is in J and it is somehow lovely in a way
-- that ordinary mortals cannot understand
-- rankOp 1 (+) A B
-- Swapping rank and depth
-- Array [2,4,5,3] Float
-- --> Array [2,5] (Array [4,3] Float)
-- And the reverse!
rankOp rank-spec f = reshape rank-spec . f . unreshape rank-spec
transpose :: Vector Nat -- Permutation of (iota (rank arg))
-> Array a -- Arg
-> Array a
-- Permutes the axes
More operations
class Item a wher
depth :: a -> Nat
instance Item Float where
depth _ = 0
instance Item a => Item (Array a) where
depth _ = 1 + depth (undefined :: a)
catenate :: Array a -> Array a -> Array a
-- Concatenates on last axis (or first in J)
-- Checks for shape compatibility
catenateA :: Axis -> Array a -> Array a -> Array a
-- You can specify the axis
-- Swapping rank with depth
flatten :: Vector (Vector a) -> Array a
vector :: [a] -> Vector a
each :: (a -> b) -> Array a -> Array b
simpleIndex -- m [a;b]
:: Array a -- a: The array to index
-> Vector (Array Nat) -- i: Outer array is a tuple
-- of length = rank a
-> Array a -- shape result = shape i[0] x shape i[1] ....
simpleIndex a is = chooseIndex a (disclose (reduce (outer catenate) zilde is))
-- We aren't quite sure about this definition
reduce :: (Array a -> Array a -> Array a) -> Array a
-- All rank one smaller than input
-> Array a -- Input
-> Array a -- Rank one smaller than input
-- except that rank 0 input gives identity
reduceA :: Axis -> (a -> a -> a) -> a
-> Array a
-> Array a -- Rank one smaller than ieput
outer :: (a -> b -> c) -- Function argument
-> Array a -> Array b -- Two array arguments, arg1, arg2
-> Array c -- Shape result = shape arg1 ++ shape arg2
-- simpleIndex a (vector [enclose 3, enclose 4]) :: Array a (rank 0)
-- mat [3 ; 4]
chooseIndex -- m [b]
:: Array a -- a: The array to index
-> Array (Vector Nat) -- i: Inner arrays are the index tuples
-- of length = rank a
-> Array a -- shape result = shape i
Various monomorphic pick operators
pick1 :: Vector (Matrix (Vector a))
-> Array (Nat, (Nat,Nat), Nat)
-> Array a
pick2 :: Vector (Matrix a)
-> Array (Nat, (Nat,Nat))
-> Array a
-- Just an instance of pick2
pick2 :: Vector (Matrix (Vector a))
-> Array (Nat, (Nat,Nat))
-> Array (Vector a)
Reference implementation
This implementation of the above API is intended to give its semantics. It is not intended to run fast!
data Array a = Arr Shape [a]
type Shape = [Nat]
-- Invariant: Arr s xs: product s = length xs
ravel :: Array a -> Vector a
ravel (Arr s a) = Arr [product s] a
zilde :: Vector a -- Empty vector, rank 1
zilde = Arr [0] []
enclose :: a -> Scalar a -- Returns a rank 0 array, of
-- depth one greater than input
enclose x = Arr [] [x]
disclose :: Scalar a -> a
disclose (Arr [] [x]) = x
discloseA (Arr outer items)
= Arr (outer ++ inner) [ i | Arr _ is <- items, i <- is ]
where
(Arr inner _ : _) = items
transpose :: Vector Nat -- Permutation of (iota (rank arg))
-> Array a -- Arg
-> Array a
transpose (Arr [n] perm) (Arr shape items)
= assert (n == length shape ) $
Arr (permute perm shape)
(scramble ... items)
-- Property: disclose (enclose x) == x
shape :: Array a -> Vector Nat
shape (Arr s a) = Arr [1] s
reshape :: Vector Nat -- s: the shape
-> Array a -- Arbitrary shape
-> Array a -- Shape of result = s
reshape (Arr [n] s) (Arr s' elts)
| null elts = error "Reshape on empty array"
| otherwise
= Arr s (take (product s) (cycle elts))
each :: (a -> b) -> Array a -> Array b
each f (Arr s xs) = Arr s (map f xs)
reduce :: (Array a -> Array a -> Array a) -> Array a
-- All rank one smaller than input
-> Array a -- Input
-> Array a -- Rank one smaller than input
-- except that rank 0 input gives identity
reduce k z (Arr [] [item])
= Arr [] [item] -- Identity on rank 0
reduce k z (Arr (s:ss) items)
= foldr k z (chop ss items)
encloseA :: Nat -> Array a -> Array a
encloseA n (Arr shape items)
= Arr outer_shape (chop inner_shape items)
where
(outer_shape, inner_shape) = splitAt n shape
chop :: Shape -> [item] -> [Array item]
chop s [] = []
chop s is = Arr s i : chop s is'
where
(i,is') = splitAt (product s) is
A couple of examples
x = 0 1 2 : Array Float = Arr [2,3] [0,1,2,3,4,5] 3 4 5
enclose x :: Array (Array Float) = Arr [] [Arr [2,3] [0,1,2,3,4,5]]