--* From postmaster%watson.vnet.ibm.com@yktvmv.watson.ibm.com Fri May 21 11:48:45 1993 --* Received: from yktvmv2.watson.ibm.com by radical.watson.ibm.com (AIX 3.2/UCB 5.64/900524) --* id AA19287; Fri, 21 May 1993 11:48:45 -0400 --* X-External-Networks: yes --* Received: from watson.vnet.ibm.com by yktvmv.watson.ibm.com (IBM VM SMTP V2R3) --* with BSMTP id 9297; Fri, 21 May 93 11:49:18 EDT --* Received: from YKTVMV by watson.vnet.ibm.com with "VAGENT.V1.0" --* id --* for asbugs@watson; Fri, 21 May 93 11:49:17 -0400 --* Received: from bernina.ethz.ch by watson.ibm.com (IBM VM SMTP V2R3) with TCP; --* Fri, 21 May 93 11:49:13 EDT --* Received: from neptune by bernina.ethz.ch with SMTP inbound id <12821-0@bernina.ethz.ch>; Fri, 21 May 1993 17:48:55 +0200 --* From: Philip Santas --* Received: from rutishauser.inf.ethz.ch (rutishauser-gw.inf.ethz.ch) by neptune id AA00500; Fri, 21 May 93 17:48:51 +0200 --* Date: Fri, 21 May 93 17:48:49 +0200 --* Message-Id: <9305211548.AA15186@rutishauser.inf.ethz.ch> --* Received: from ru7.inf.ethz.ch.rutishauser by rutishauser.inf.ethz.ch id AA15186; Fri, 21 May 93 17:48:49 +0200 --* To: asbugs@watson.ibm.com --* Subject: functional.as --@ Fixed by: SSD Wed Dec 08 10:13:51 1993 --@ Tested by: none --@ Summary: The compile-time errors listed either don't happen (i.e. v33 now compiles the expressions) or involve misunderstandings about product types in A#. (i.e. A# correctly reports an error) --Functional.as ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++ Author: Philip S. Santas ++ Date Created: 18 May 1939 ++ Date Last Updated: 20 May 1990 ++ Basic Operations: map, foldleft, foldright, seq, pairself, K, I ++ secr, curry, uncurry, apl, apr, ++ flat, subset, setInsert, front, nthTail, ++ filter, takewhile, dropwhile, ++ depth, breadth (for backtracking) ++ ++ Related Constructors: ++ Also See: queens.as, missionaries.as ++ AMS Classifications: ++ Keywords: functional, lists, parametric polymorphism, currying, backtracking ++ References: ++ Description: The code is devided in 3 Parameterized Modules ++ Power(S) defines funpow ++ Fold(S,T) defines polymorphic general purpose functios like ++ map: (S->T)->(List S)->(List T) ++ foldright: ((S,T) -> T) -> (List S, T) -> T ++ etc. ++ SECR(S,T,Y) defines operations for currying,like ++ curry (f:(S,T)->Y)(x:S)(y:T):Y == f(x,y) ++ uncurry (f:S->T->Y)(x:S,y:T):Y == (f x) y ++ LoopList(T) includes functions that can be added to the ListCategory ++ Some of them perform ierations like: ++ takewhile: (T->B)->(List T)->(List T) ++ Others implement operations on sets, like: ++ union: (List T, List T) -> (List T) ++ Additionaly we have operators for logic, such as: ++ depth: (T -> List T, T -> Bit) -> T -> (List T) ++ for depth-first search (similar for breadth-first, etc.) ++ ++ Compiler-Errors: The functions ++ app: (S->T)->(List S)->() ++ combine: (List S, List T) -> (List (S,T)) ++ combineR: (List S, List T) -> (List (T,S)) ++ split: (List (T,S)) -> (List S, List T) ++ partition: (T->Bit)->(List T)->(List T,List T) ++ depthfirst: (T -> List T, T -> B) -> T -> (List T) ++ breadthfirst: (T -> List T, T -> B) -> T -> (List T) ++ have been commented out because they cause compile time ++ errors (this indicates compiler bugs) ++ Additional examples: There is an additional definition for ++ flat: (List List T) -> (List T) ++ which compiles properly. ++ Applications can be found in queens.as (compiles, runs) ++ and missionaries.as (type-checks, but does not compile) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ #include "aslib.as" SI ==> SingleInteger B ==> Bit import SI import B Power(S: with Object): with funpow: SI -> (S->S) -> S -> S ++ funpow n f x applies n times f to x == add funpow(n:SI)(f:S->S)(x:S):S == n<=0 => x ((funpow (n-1)) f) (f x) Fold(S: with Object, T: with Object): with map: (S->T)->(List S)->(List T) seq: (S->T)->(List S)->T -- app: (S->T)->(List S)->() foldleft: ((S,T) -> S) -> (S, List T) -> S foldright: ((S,T) -> T) -> (List S, T) -> T K: S->T->S ++ K is the famous lambda-combinator I: S->S Kf: (S,T)->S Ks: (S,T)->T pairself: (S->T) -> (S,S) -> (T,T) -- combine: (List S, List T) -> (List (S,T)) -- combineR: (List S, List T) -> (List (T,S)) -- split: (List (T,S)) -> (List S, List T) orelf: (S->T, S->T) -> S->T == add import List T import List S map(f:S->T)(l:List S):(List T) == [f(i) for i in l] seq(f:S->T)(l:List S):(List T) == f(i) for i in l -- app(f:S->T)(l:List S):(List T) == f(i) for i in l; () foldleft(f:(S,T) -> S) (e:S, ll: List T): S == empty? ll => e (foldleft f) (f(e,(first ll)), rest ll) foldright(f:(S,T) -> T) (ll: List S, e:T): T == empty? ll => e f(first ll, (foldright f) (rest ll, e)) K(x:S)(y:T):S == x Kf(x:S,y:T):S == x Ks(x:S,y:T):T == y I(x:S):S == x pairself(f:S->T)(x:S, y:S):(T,T) == (f x, f y) -- combine(l1:List S, l2: List T): List (S,T) == -- l1=nil => nil -- l2=nil => nil -- cons((first l1, first l2), combine(rest l1, rest l2)) -- combineR(l1:List S, l2: List T): List (T,S) == -- combine(l2, l1) -- split(ll: List (T,S)):(List T, List S) == -- (map first ll, map second ll) orelf(f:S->T, g:S->T):S->T == (x:S):T +-> f x SECR(S: with Object, T: with Object, Y: with Object): with secr: ((S,T)->Y)->T->S->Y curry: ((S,T)->Y)->S->T->Y uncurry: ((S,T)->Y)->(S,T)->Y apl: (S, (S, T)->Y) -> T -> Y apr: ((S,T)->Y, T) -> S -> Y == add import S import T import Y curry (f:(S,T)->Y)(x:S)(y:T):Y == f(x,y) uncurry (f:S->T->Y)(x:S,y:T):Y == (f x) y secr(f:(S,T)->Y)(y:T)(x:S):Y == f(x,y) apl(x:S, f:(S,T)->Y)(y:T):Y == f(x,y) apr(f:(S,T)->Y, y:T)(x:S):Y == f(x,y) LoopList(T:with Object): with isfull: SI -> (List T) -> B front: (SI, List T) -> (List T) nthTail: (SI, List T) -> (List T) setInsert: (T, List T) -> (List T) union: (List T, List T) -> (List T) intersect: (List T, List T) -> (List T) subset: (List T, List T) -> B flat: (List List T) -> (List T) remove: (List T, T) -> (List T) filter: (T->B)->(List T)->(List T) takewhile: (T->B)->(List T)->(List T) dropwhile: (T->B)->(List T)->(List T) depth: (T -> List T, T -> B) -> T -> (List T) breadth: (T -> List T, T -> B) -> T -> (List T) -- partition: (T->B)->(List T)->(List T,List T) -- depthfirst: (T -> List T, T -> B) -> T -> (List T) -- breadthfirst: (T -> List T, T -> B) -> T -> (List T) == add import List T import List List T isfull (n:SI) (ll:List T): B == #ll = n front(n:SI, ll: List T): List T == empty? ll => nil n=0 => nil #ll <= n => ll cons(first ll, front(n-1, rest ll)) nthTail(n:SI, ll: List T): List T == empty? ll => nil n=0 => nil nthTail(n-1, rest ll) setInsert(elem: T, ll:List T):List T == member?(elem, ll) => ll cons(elem, ll) union(l1: List T, l2: List T):List T == empty? l1 => l2 empty? l2 => l1 union(rest l1, setInsert(first l1, l2)) intersect(l1: List T, l2: List T):List T == empty? l1 => nil member?(first l1, l2) => cons(first l1, intersect(rest l1, l2)) intersect(rest l1, l2) subset(l1: List T, l2: List T):B == empty? l1 => true member?(first l1, l2) and subset(rest l1, l2) flat(ll: List List T): List T == empty? ll => nil concat(first ll, flat rest ll) -- flat(ll: List List T): List T == -- import Fold(List T, List T) -- (foldright concat) (ll, nil) -- VERY NICE! remove(ll:List T, elem: T): List T == empty? ll => nil (first ll) = elem => rest ll cons(first ll, remove(rest ll, elem)) filter(pred: T->B) (ll: List T): (List T) == empty? ll => nil pred(first ll) => cons(first ll, (filter pred) (rest ll)) (filter pred) (rest ll) takewhile(pred: T->B) (ll: List T): (List T) == empty? ll => nil pred(first ll) => cons(first ll, (takewhile pred) (rest ll)) nil$(List T) dropwhile(pred: T->B) (ll: List T): (List T) == empty? ll => nil pred(first ll) => (dropwhile pred) (rest ll) ll -- localpart(l: List T, answer:(List T,List T))(pred: T->B):(List T,List T) == -- empty? l => answer -- pred(first l) => (localpart(rest l, (cons(first l, answer 1), answer 2))) pred -- (localpart(rest l, (answer 1, cons(first l, answer 2)))) pred -- partition(pred:T->B)(ll:List T):(List T,List T) == -- (localpart(reverse ll, (nil, nil))) pred localdfs(nex: T->List T, pred: T->B)(x:T)(ll: List T):List T == empty? ll => nil pred (first ll) => cons(first ll, ((localdfs (nex, pred)) x) concat(nex first ll, rest ll)) ((localdfs (nex, pred)) x) concat(nex first ll, rest ll) depth(nex: T->List T, pred: T->B)(x:T):List T == ((localdfs (nex, pred)) x) [x] -- depthfirst(nex: T->List T, pred: T->B)(x:T):List T == -- dfs(ll:List T):List T == -- empty? ll => nil -- pred (first ll) => cons(first ll, dfs concat(nex first ll, rest ll)) -- dfs concat(nex first ll, rest ll) -- dfs [x] localbfs(nex: T->List T, pred: T->B)(x:T)(ll: List T):List T == empty? ll => nil$(List T) pred (first ll) => cons(first ll, ((localbfs (nex, pred)) x) concat(rest ll, nex first ll)) ((localdfs (nex, pred)) x) concat(nex first ll, rest ll) breadth(nex: T->List T, pred: T->B)(x:T):List T == ((localbfs (nex, pred)) x) [x] -- breadthfirst(nex: T->List T, pred: T->B)(x:T):List T == -- bfs(ll:List T):List T == -- empty? ll => nil -- pred (first ll) => cons(first ll, bfs concat(rest ll, nex first ll)) -- bfs concat(rest ll, nex first ll) -- bfs [x] -- depthiter(nex: T->List T, pred: T->B)(x:T):List T == -- import Fold(T, List T) -- dfs(kk:SI)(y:T, sf:List T): List T == -- if kk=0 -- then if pred y -- then cons(y,sf) -- else sf -- else (foldright (dfs (kk-1))) (nex y, sf) -- deepen(k:SI): List T == (dfs k) (x, deepen (k+1)) -- deepen 0