The following functions are written in my strict, weakly typed language Navel.
They enable the pure functional representation of queue disciplined structures:
def qupdate key value rest =
lam k v.(if k=key
then value:(qupdate key value rest)
else
let newvalue:newrest = rest k v
in newvalue:(qupdate key value newrest));
def qextend key value = value:(qupdate key value qextend);
[ : == list concatenation
- used here for structure matching - no tuples in Navel... ]
Such a function applied to a key and value will either
a) if the key is unknown, extend itself at the end with a new association
for the key and value, returning the value and the extended version of itself
or
b) if the key is known, return the already associated value and the original
function
For example:
qextend 1 1 == 1:(qupdate 1 1 qextend)
(qupdate 1 1 qextend) 2 4 == 4:(qupdate 1 1 (qupdate 2 4 qextend))
(qupdate 1 1 (qupdate 2 4 qextend)) 3 9 ==
9:(qupdate 1 1 (qupdate 2 4 (qupdate 3 9 qextend)))
(qupdate 1 1 (qupdate 2 4 (qupdate 3 9 qextend))) 2 5 ==
4:(qupdate 1 1 (qupdate 2 4 (qupdate 3 9 qextend)))
I have other functions which are tree disciplined, and updateable queue
disciplined but constant space on the number of unique keys.
They're used in pure functional language implementations from denotational
semantics to try and get round the inefficiencies of the traditional
stack disciplined update functions.
I don't think the direct Haskell equivalents can be typed by current systems?
I don't think that there are typeable Haskell equivalents without using layers
of concrete datatypes?
Greg Michaelson
