Maude-help mailing list

[Steven Eker <eker AT csl.sri.com>]

Hi Muharram,

Assuming you are using the current release (2.2) and you want to do this 
computation efficiently (O(n log n) element comparisons), I would recommend 
recursing though the list, keeping an array indexed by elements of the 
current count for each element:

fmod COUNT-LIST{X :: TRIV} is
  pr LIST{X} .  *** list of elements to be counted
  pr LIST{Nat} .  *** list of counts
  pr ARRAY{X, Nat0} .  *** array of counts indexed by elements

  var E : X$Elt .
  var L : List{X} .
  var A : Array{X, Nat0} .

  *** this function does the work
  op countListAux : List{X} Array{X, Nat0} -> List{Nat} .
  eq countListAux(E L, A) =
    (A[E]) countListAux(L, insert(E, (A[E]) + 1, A)) .
  eq countListAux(nil, A) = nil .

  *** this function provides a clean interface
  op countList : List{X} -> List{Nat} .
  eq countList(L) = countListAux(L, empty) .
endfm

To test this we just instantiate it using the String view:

fmod TEST is
  pr  COUNT-LIST{String} .
endfm

red  countList("A" "A" "B" "C" "A" "A" "C" "D" "B" "A" "B" "B" "D") .

which produces:
rewrites: 80 in 0ms cpu (0ms real) (~ rewrites/second)
result NeList{Nat}: 0 1 0 0 2 3 1 0 1 4 2 3 1

Best regards,
Steven Eker

On Tuesday 07 March 2006 07:35, MANSOORM wrote:
> Hi there,
> In a list of multi-type elements,
> I want to mark the elements of the same type with an ascending counter.
> That is, each element anywhere in the list takes a label that indicates
> how many elements of the same type exist before this one.
> following is an example:
> The list: [ A A B C A A C D B A B B D ]
> Corresponding
> counter labels: [ 0 1 0 0 2 3 1 0 1 4 2 3 1 ]
> How do I this with maude ?
>
> Any help is appreciated
> --------------------------
> Muharram Mansoorizadeh
> Ph.D. Student,Computer Sci.
> TMU-TEHRAN,IRAN
> http://www.modares.ac.ir
>
>
> _______________________________________________
> Maude-help mailing list
> Maude-help AT maude.cs.uiuc.edu
> http://maude.cs.uiuc.edu/cgi-bin/mailman/listinfo/maude-help