DEFINE

(* This is an example association list from doc id to word id list.  

   We use integer word ids instead of quoted strings because joy has a strong 
   bias towards working with numbers (e.g. the "in" function only works with 
   numbers).  To make it easy to distinguish doc ids from word ids, the word 
   ids are all in the nineties. *)
docs_to_words ==
	[ [1 [90 91 92]] 
          [2 [90 91]] 
          [3 [90]]
	  [4 []]
	];

(* invert :: docs_to_words -> words_to_docs *)
(* takes an association list from docs to words, returns an association
   list from words to docs *)
invert == 
	dup word_list
	[ dup rollup 		(* save the word, so we can cons it later *)
	  docs_with_word
	  mklist cons]		(* combine the word and the docs list *)
	map;

(* doc_list :: docs_to_words -> docs *)
(* returns the set of all documents in the list *)
doc_list ==
	[first] map;		(* just keep the doc ids *)

(* word_list :: docs_to_words -> words *)
(* returns the union of all words in all docs *)
word_list ==
	[rest first] map 	(* strip off the doc ids *)
	[] [concat] fold	(* concat all the word lists *)
	nub;			(* remove duplicate words *)

(* docs_with_word :: docs_to_words word -> docs *)
docs_with_word == 
	swap
	[rest first in] filter	(* remove docs that don't have the given word *)
	doc_list;		(* *)

(* nub :: list -> list *)
(* Removes duplicate elements in a list.  The name "nub" comes from the 
   function of the same name in haskell.  This implementation is O(n^2) *)
nub ==
	[] 		(* the accumulator begins as an empty list *)
	[ [swap in] 	(* if the current element is already in the list, *)
	  [pop] 	(* ignore it *)
	  [swons] 	(* otherwise add it to the list *)
	  ifte]
	fold;

(* mklist :: x -> [x] *)
(* creates a one-element list containing the first item on the stack *)
mklist ==
	[] cons;

END.

(* test the invert function.  This should produce:
   [ [92 [1]]   [91 [1 2]]   [90 [1 2 3]] ]
*)
docs_to_words invert.