//
//------------------ DOK FILE --------------------------------------------------
+Header	listLib
=pkg	bios
=title	Lists
=short	the prefered structure of functional languages
=desc	Lists are a major structure for functional languages. They are unmutable ordered sets of elements of any type.
//
//
//------------------ PROTO ----------------------------------------------------- list
+Proto	list
=type	list a1
=mode	type
=pkg	language
=impl	mcy
=link	
=desc
Lists are a major structure for functional languages. They are unmutable ordered sets of elements of any type.
It is possible to write lists directly in the minimacy source code. This is how the list appears when Minimacy displays types::
	1::2::3::nil
	"foo"::"bar"::nil
All list items must have the same type.
nil is the empty list. Don't forget it!
//
//
//------------------ PROTO ----------------------------------------------------- listConcat
+Proto	listConcat
=type	fun list a1 list a1 -> list a1
=mode	function
=pkg	bios
=impl	mcy
=link	
=desc
This function returns the concatenation of two lists of the same type. It doesn't affect the initial lists.
	> listConcat (1::2::3::nil, 4::5::nil)
>-> list Int:
>   Int: 1 (0x1)
>   Int: 2 (0x2)
>   Int: 3 (0x3)
>   Int: 4 (0x4)
>   Int: 5 (0x5)
//
+arg	p
=type	list a1
=desc	A list
//
+arg	q
=type	list a1
=desc	Another list with the same type
//
+arg	result
=type	list a1
=desc	The concatenation of list p and list q, in this order
//
//
//------------------ PROTO ----------------------------------------------------- listGet
+Proto	listGet
=type	fun list a1 Int -> a1
=mode	function
=pkg	bios
=impl	mcy
=link	
=desc
This function returns the element of the list src which is at the position index.
The first element has index 0. If the index is negative or higher than the length of the list, it returns nil.

	> listGet (1::2::3::nil, 2)
>-> Int: 3 (0x3)
//
+arg	src
=type	list a1
=desc	A list
//
+arg	index
=type	Int
=desc	A position in the list, starting from 0
//
+arg	result
=type	a1
=desc	The element at the position index in the list
//
//
//------------------ PROTO ----------------------------------------------------- listLast
+Proto	listLast
=type	fun list a1 -> a1
=mode	function
=pkg	bios
=impl	mcy
=link	
=desc
This function returns the last element of the list src, or nil if src is emtpy.
	> listLast (1::2::3::nil)
>-> Int: 3 (0x3)
//
+arg	src
=type	list a1
=desc	A list
//
+arg	result
=type	a1
=desc	The last element of the list src
//
//
//------------------ PROTO ----------------------------------------------------- listLength
+Proto	listLength
=type	fun list a1 -> Int
=mode	function
=pkg	bios
=impl	mcy
=link	
=desc
This function returns the number of elements in the list, or 0 if src is empty.
	> listLength (1::2::3::nil)
>-> Int: 3 (0x3)
//
+arg	src
=type	list a1
=desc	A list
//
+arg	result
=type	Int
=desc	The length of the list src
//
//
//------------------ PROTO ----------------------------------------------------- listMatchHead
+Proto	listMatchHead
=type	fun list list a1 a1 -> list a1
=mode	function
=pkg	bios
=impl	mcy
=link	
=desc
This function searches in a list of lists to find the list which starts with the value key.
	> listMatchHead ((1::2::3::nil)::(4::5::6::nil)::(7::8::nil)::nil, 4)
>-> list Int:
>   Int: 5 (0x5)
>   Int: 6 (0x6)
//
+arg	src
=type	list list a1
=desc	A list of lists
//
+arg	key
=type	a1
=desc	A value with the same type as the elements of the list of lists src
//
+arg	result
=type	list a1
=desc	A list
//
//
//------------------ PROTO ----------------------------------------------------- arrayFromList
+Proto	arrayFromList
=type	fun list a1 -> array a1
=mode	function
=pkg	bios
=impl	mcy
=link	
=desc
This function creates an array containing the elements of the list src in the ordre of the list.
	> arrayFromList (1::2::3::nil)
>-> array Int: #3 {
>   0:
>     Int: 1 (0x1)
>   1:
>     Int: 2 (0x2)
>   2:
>     Int: 3 (0x3)
>}
This is the opposite of the [[listFromArray]] function.
//
+arg	src
=type	list a1
=desc	A list
//
+arg	result
=type	array a1
=desc	An array containing as many elements as the list src
//
//
//------------------ PROTO ----------------------------------------------------- head
+Proto	head
=type	fun list a1 -> a1
=mode	function
=pkg	bios
=impl	native
=link	
=desc
This function returns the first element of the list src, or nil if src is empty.
	> head (1::2::3::nil)
>-> Int: 1 (0x3)
//
+arg	src
=type	list a1
=desc	A list
//
+arg	result
=type	a1
=desc	The first element of the list src
//
//
//------------------ PROTO ----------------------------------------------------- listContains
+Proto	listContains
=type	fun list a1 a1 -> Bool
=mode	function
=pkg	bios
=impl	mcy
=link	
=desc
This function looks for an element in the list src and returns true if it finds it, else returns nil.
	> listContains (1::2::3::nil, 2)
>-> Bool: true
//
+arg	src
=type	list a1
=desc	A list
//
+arg	element
=type	a1
=desc	An element with the same type of the elements of the list src
//
+arg	result
=type	Bool
=desc	true if element is found in the list src
//
//
//------------------ PROTO ----------------------------------------------------- listFilter
+Proto	listFilter
=type	fun list a1 (fun a1 -> Bool) -> list a1
=mode	function
=pkg	bios
=impl	mcy
=link	
=desc
This function filters the list src. It applies the fKeep function to each element of the list, and puts it in the filtered list only when the fKeep function returns true.
	> listFilter (1::2::3::nil, lambda (val) = val>1)
>-> list Int:
>   Int: 2 (0x2)
>   Int: 3 (0x3)
//
+arg	src
=type	list a1
=desc	A list
//
+arg	fKeep
=type	fun a1 -> Bool
=desc	A function which filters elements and returns true when the argument must be kept
//
+arg	result
=type	list a1
=desc	The filtered list
//
//
//------------------ PROTO ----------------------------------------------------- listInsert
+Proto	listInsert
=type	fun list a1 a1 (fun a1 a1 -> Bool) -> list a1
=mode	function
=pkg	bios
=impl	mcy
=link	explicit
=desc
This function returned an ordered list made of the elements of src and the element to insert p.
	> listInsert (1::2::5::nil, 3, lambda (p, q)=p<q) 
>-> list Int:
>   Int: 1 (0x1)
>   Int: 2 (0x2)
>   Int: 3 (0x3)
>   Int: 5 (0x5)
//
+arg	src
=type	list a1
=desc	A list
//
+arg	p
=type	a1
=desc	An element to insert in the list
//
+arg	fBefore
=type	fun a1 a1 -> Bool
=desc	A lambda function which is called with two elements from the list and returns a boolean
//
+arg	result
=type	list a1
=desc	An ordered list
//
//
//------------------ PROTO ----------------------------------------------------- listFind
+Proto	listFind
=type	fun list a1 (fun a1 -> Bool) -> a1
=mode	function
=pkg	bios
=impl	mcy
=link	
=desc
This function looks for an element in the list src. It applies the fFound function to each element of the list in the order of the list.
When fFound returns true for an element, the function stops and return the element. It returns nil when it doesn't find the element.
	> listFind (1::2::3::nil, lambda (val) = val==2)
>-> Int: 2 (0x2)
//
+arg	src
=type	list a1
=desc	A list
//
+arg	fFound
=type	fun a1 -> Bool
=desc	A function which is applied to the elements of the list src and returns a boolean
//
+arg	result
=type	a1
=desc	The first element of list src for which fFound returns true
//
//
//------------------ PROTO ----------------------------------------------------- listMap
+Proto	listMap
=type	fun list a1 (fun a1 -> a2) -> list a2
=mode	function
=pkg	bios
=impl	mcy
=link	
=desc
This function converts the elements of the list src, by applying fMap to each of them.
When fMap returns nil, the element is ignored.
	> listMap (1::2::3::nil, lambda (val) = if val>2 then val*10 else nil)
>-> list Int:
>   Int: 10 (0xA)
>   Int: 30 (0x1E)
//
+arg	src
=type	list a1
=desc	A list
//
+arg	fMap
=type	fun a1 -> a2
=desc	A function which is applied to the elements of the list src and returns any element
//
+arg	result
=type	list a2
=desc	A list whose elements are the result of the fMap function on the elements of the list src
//
//
//------------------ PROTO ----------------------------------------------------- quicksort
+Proto	quicksort
=type	fun list a1 (fun a1 a1 -> Bool) -> list a1
=mode	Function
=pkg	bios
=impl	mcy
=link	
=desc
This function applies the quicksort algorithm to the list src, using the lambda function fBefore to compare elements.
	> quicksort (3::2::5::4::nil, lambda (a, b)=a<b)
>-> list Int:
>   Int: 2 (0x2)
>   Int: 3 (0x3)
>   Int: 4 (0x4)
>   Int: 5 (0x5)
//
+arg	src
=type	list a1
=desc	A list
//
+arg	fBefore
=type	fun a1 a1 -> Bool
=desc	A lambda function which returns true if the first element should be before the second
//
+arg	result
=type	list a1
=desc	The ordered list
//
//
//------------------ PROTO ----------------------------------------------------- listReduce
+Proto	listReduce
=type	fun list a1 a2 (fun a2 a1 -> a2) -> a2
=mode	function
=pkg	bios
=impl	mcy
=link	
=desc
This function apply a reduce function to a list.
-	The fReduce function is applied to v0 and the first element of the list src
-	The fReduce function is applied to this result and the second element of the list
-	and again until the end of the list

It makes it easy to compute the max element of a list:
	> listReduce (1::2::5::3::nil, 0, #max)
>-> Int: 5 (0x5)

Another example to compute the sum of all the elements of a list:
	> listReduce (1::2::5::3::nil, 0, lambda (v0, v)=v0+v)
>-> Int: 11 (0xB)
//
+arg	src
=type	list a1
=desc	A list
//
+arg	v0
=type	a2
=desc	The initial result
//
+arg	fReduce
=type	fun a2 a1 -> a2
=desc	A function which is applied iteratively to the current result and the next element in the list src.
//
+arg	result
=type	a2
=desc	The final result
//
//
//------------------ PROTO ----------------------------------------------------- listRemove
+Proto	listRemove
=type	fun list a1 a1 -> list a1
=mode	function
=pkg	bios
=impl	mcy
=link	
=desc
This function removes an element from a list. The original list is not modified.
	> listRemove (1::2::3::nil, 2)
>-> list Int:
>   Int: 1 (0x1)
>   Int: 3 (0x3)
//
+arg	src
=type	list a1
=desc	A list
//
+arg	element
=type	a1
=desc	An element
//
+arg	result
=type	list a1
=desc	A copy the list src without the element.
//
//
//------------------ PROTO ----------------------------------------------------- listReverse
+Proto	listReverse
=type	fun list a1 -> list a1
=mode	function
=pkg	bios
=impl	mcy
=link	
=desc
This function is used to reverse the order of a list.
	> listReverse (1::2::3::nil)
>-> list Int:
>   Int: 3 (0x3)
>   Int: 2 (0x2)
>   Int: 1 (0x1)
//
+arg	p
=type	list a1
=desc	A list
//
+arg	result
=type	list a1
=desc	A new list
//
//
//------------------ PROTO ----------------------------------------------------- listTest
+Proto	listTest
=type	fun list a1 (fun a1 -> Bool) -> Bool
=mode	function
=pkg	bios
=impl	mcy
=link	explicit
=desc
This function is based on the find function. It returns true if and only if the fTest function returns true for at least one element of the list src. 
	> listTest (1::2::3::nil, lambda (val) = val==2)
>-> Bool: true
//
+arg	src
=type	list a1
=desc	A list
//
+arg	fTest
=type	fun a1 -> Bool
=desc	A function which is applied to the elements of the list src and returns a boolean
//
+arg	result
=type	Bool
=desc	A boolean
//
//
//------------------ PROTO ----------------------------------------------------- tail
+Proto	tail
=type	fun list a1 -> list a1
=mode	function
=pkg	bios
=impl	native
=link	
=desc
This function complements the [[head]] function. It returns the list src without its first element, or nil if src is empty.
	> tail (1::2::3::nil)
>-> list Int:
>   Int: 2 (0x3)
>   Int: 3 (0x2)
//
+arg	src
=type	list a1
=desc	A list
//
+arg	result
=type	list a1
=desc	The list without its first element
//
//
//------------------ PROTO ----------------------------------------------------- tripleListCompress
+Proto	tripleListCompress
=type	fun list list list a1 -> list a1
=mode	function
=pkg	bios
=impl	mcy
=link	
=desc
This function concatenates all the elements contained in src.
	> tripleListCompress( ((1::2::nil)::(3::nil)::nil):: ((4::nil)::(5::nil)::nil):: nil)
>-> list Int:
>   Int: 1 (0x1)
>   Int: 2 (0x2)
>   Int: 3 (0x3)
>   Int: 4 (0x4)
>   Int: 5 (0x5)
//
+arg	src
=type	list list list a1
=desc	A list of lists of lists of elements
//
+arg	result
=type	list a1
=desc	The list of every elements in src
//
//
//------------------ PROTO ----------------------------------------------------- listVisit
+Proto	listVisit
=type	fun list a1 (fun a1 -> Bool) -> Bool
=mode	function
=pkg	bios
=impl	mcy
=link	
=desc
This function visits the elements of the list src in the order of the list.
For each element it evaluates the fVisit function. It stops when fVisit doesn't return true.
	> listVisit (1::2::3::nil, lambda (val) = echoLn val; val!=2)
>1
>2
>-> Bool: nil
//
+arg	src
=type	list a1
=desc	A list
//
+arg	fVisit
=type	fun a1 -> Bool
=desc	A function which is applied to the elements of the list src and returns a boolean
//
+arg	result
=type	Bool
=desc	true if the visit reaches the end of the list src
//
//
//------------------ PROTO ----------------------------------------------------- doubleListCompress
+Proto	doubleListCompress
=type	fun list list a1 -> list a1
=mode	function
=pkg	bios
=impl	mcy
=link	
=desc
This function concatenates all the elements contained in src.
	> doubleListCompress ((1::2::3::nil):: (4::5::nil):: nil)
>-> list Int:
>   Int: 1 (0x1)
>   Int: 2 (0x2)
>   Int: 3 (0x3)
>   Int: 4 (0x4)
>   Int: 5 (0x5)
//
+arg	src
=type	list list a1
=desc	A list of lists of elements
//
+arg	result
=type	list a1
=desc	The list of every elements in src
//
//
//------------------ PROTO ----------------------------------------------------- listPosition
+Proto	listPosition
=type	fun list a1 a1 -> Int
=mode	Function
=pkg	bios
=impl	mcy
=link	
=desc	
This function returns the position of an element in a list.
	> listPosition (2::4::3::7::nil, 3)
>-> Int: 2 (0x2)

	> listPosition (2::4::3::7::nil, 8)
>-> Int:  nil
//
+arg	src
=type	list a1
=desc	A list of elements
//
+arg	val
=type	a1
=desc	The element to search
//
+arg	result
=type	Int
=desc	The index of the element in the list, starting from 0. [[nil]] if the element is not in the list.
//
//
//------------------ PROTO ----------------------------------------------------- listCut
+Proto	listCut
=type	fun list a1 Int -> list a1
=mode	Function
=pkg	bios
=impl	mcy
=link	
=desc	
This function "cuts" an input list so that it has at most 'length' elements. 
	> listCut (2::4::3::7::nil, 2)
>-> list Int:
>   Int: 2 (0x2)
>   Int: 4 (0x4)

	> listCut (2::4::3::7::nil, 0)
>-> list Int:  nil
//
+arg	src
=type	list a1
=desc	A list of elements
//
+arg	length
=type	Int
=desc	The maximum size of the resulting list
//
+arg	result
=type	list a1
=desc	A list made of the first 'length' elements from the input list
//
//
//------------------ PROTO ----------------------------------------------------- listSkip
+Proto	listSkip
=type	fun list a1 Int -> list a1
=mode	Function
=pkg	bios
=impl	mcy
=link	
=desc	
This function returns the input list after a given number of elements.
	> listSkip (2::4::3::7::nil, 2)
>-> list Int:
>   Int: 3 (0x3)
>   Int: 7 (0x7)
//
+arg	src
=type	list a1
=desc	A list of elements
//
+arg	offset
=type	Int
=desc	The number of elements to skip
//
+arg	result
=type	list a1
=desc	A list made by removing the first 'offset' elements from the input list