;N seq.cam - a CAMILA library for the A-seq functor

;A J.N. Oliveira (jno@di.uminho.pt)

;D
; This library adds extra functionality to the CAMILA built-in 
; polymorphic finite sequence data type F(X)=X-seq.
; Last Update: 1999.11.11
;E

FUNC seqCata(c:B,f:AxB->B,l:A-seq):B
;
; seqCata(c,f,l) is the standard catamorphism on finite sequences
; 
RETURN if l==<> then c else f(hd(l),seqCata(c,f,tl(l)));

FUNC seqInseg(n:NAT):NAT-seq
;
; seqInseg(n) is the sequence version of inseg(n).
; Thus elems(seqInseg(n)) == inseg(n).
;
RETURN if n==0 then <> else seqInseg(n.-1) ^ <n>;

FUNC seqSubl(l:A-seq,i:NAT,n:NAT0):A-seq
;
; seqSubl(l,i,n) selects from l its n-element-long subsequence,
; from the ith position onwards, or as much as possible if l is too
; short.
;
RETURN if n==0 then <>
       else if l == <> then <>
       else let (h=hd(l), t=tl(l))
            in if i==1 then <h>^seqSubl(t,i,n.-1)
                       else seqSubl(t,i.-1,n);

FUNC seqAddSep(l:A-seq,a:A):A-seq
;
; seqAddSep(l,a) inserts a as a separator in l.
; For instance, seqAddSep(<c,d,a>,a) == <c,a,d,a,a>.
;
RETURN if l==<> then <>
                else < hd(l) > ^ CONC(< < a,x > | x <- tl(l) > ); 

FUNC seq2mset(l:A-seq):A->NAT 
;
; seq2mset(l) converts l into the multiset of its elements.
; So, order is lost but not multiplicity.
; Thus facts
; dom(seq2mset(l)) == elems(l) and
; mseSumRan(seq2mset(l)) == length(l)
; hold.
;
RETURN [ x -> length(< y | y <- l: y==x >) | x <- elems(l) ];

FUNC seqInv(l:A-seq):A-seq
;
; seqInv(l) is l in reverse order.
; Thus elems(seqInv(l)) == elems(l) and
; seqInv(seqInv(l)) == l are valid properties of seqInv.
;
RETURN if l==<> then <> else seqInv(  tl(l)) ^ < hd(l) >;

FUNC seqBlast(l:A-seq):A-seq
;
; seqBlast(l) keeps all elements of l but the last one.
;
RETURN seqInv(tl(seqInv(l)));

FUNC seq2mseSeq(l:A-seq):(A->NAT)-seq
;
; seq2mseSeq(l) converts l into the corresponding sequence of unitary
; multisets, which may be useful in a data-mining context.
;
RETURN  < [ x -> 1 ] | x <- l >;

FUNC set2seq(s:A-set):A-seq
;
; The "inverse" of elems...
;
RETURN < a | a <- s >;

FUNC seq2ff(l:A-seq):NAT->A
;
; seq2ff(l) converts sequence l into a finite mapping keeping track
; of the original element positions.
; Thus properties dom(seq2ff(l))==inseg(length(l))
; and seq2ff(l)[i]== l(i) hold.
;
RETURN [ x -> nth(x,l) | x <- inseg(length(l)) ];

FUNC seqSplit(l:A-seq,n:NAT):(A-seq)-seq
;
; seqSplit(l,n) partitions l into the sequence of its subsequences
; of fixed length n (except possibly the last).
; Therefore, CONC(seqSplit(l,n)) == l holds.
;
RETURN let (c=length(l),
            i=c./n,
            m=if rem(c,n)==0 then i else i.+1)
       in < seqSubl(l,(j.-1).*n.+1,n) | j <- seqInseg(m) >;

FUNC seqDiff(s:A-seq,r:A-seq):A-seq
;
; seqDiff(s,r) computes the subsequence of l which does not contain any
; element of r.
; So, elems(seqDiff(s,r)) == elems(s) - elems(r).
;
RETURN < a | a <- s: ~(a in elems(r))>;

FUNC seqUpdate(x:A,d:B,l:A-seq):A-seq
;
; seqUpdate forces every x to d in l
;
RETURN < if a==x then d else a | a <- l > ;