/*
 * list.lmn - List module
 *
 *   Copyright (c) 2008, Ueda Laboratory LMNtal Group <lmntal@ueda.info.waseda.ac.jp>
 *   All rights reserved.
 *
 *   Redistribution and use in source and binary forms, with or without
 *   modification, are permitted provided that the following conditions are
 *   met:
 *
 *    1. Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *
 *    2. Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in
 *       the documentation and/or other materials provided with the
 *       distribution.
 *
 *    3. Neither the name of the Ueda Laboratory LMNtal Group nor the
 *       names of its contributors may be used to endorse or promote
 *       products derived from this software without specific prior
 *       written permission.
 *
 *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * $Id: boolean.lmn,v 1.3 2008/09/19 05:55:21 taisuke Exp $
 */


/**
NAME
	List module

SYNOPSIS


AUTHOR
	Koji Hara

HISTORY
	2004/05/22(Sat)
    2008/09/18(Sat) Javaのインラインを使用している部分を削除
*/

{
module(list).

/**
 * list.new(-Res):
 *
 * Returns an empty list.
 * @param -Res  the result (empty list)
 */
H=list.new :- H=[].

/**
 * list.is_empty(+List, -Res, -NewList)
 * 
 * Res is bound to true if List is empty, false otherwise.
 * @param +List list
 * @param -Res  true/1 or false/1
 * @param -NewList the original list (unchanged)
 * @example r=list.is_empty([],R), ret=R ==> r=[], ret=true
 */
H=list.is_empty([], Return) :- H=[], Return=true.
H=list.is_empty('.'(Value, Next), Return) :- H='.'(Value, Next), Return=false.

/*
 * list.unshift(+List, +Obj, -NewList)
 *
 * リストListの先頭にObjを格納します。
 * @param +List リスト
 * @param +Obj 先頭に格納する要素
 * @param -NewList 更新されたリスト
 */
// H=list.unshift([], Obj) :- H='.'(Obj, []).
// H=list.unshift('.'(Value, Next), Obj) :- H='.'(Obj, '.'(Value, Next)).


/*
 * list.shift(+List, -Ret, -NewList)
 *
 * リストListの先頭要素を取り出します。
 * @param +List リスト
 * @param -Ret 取り出された要素
 * @param -NewList 更新されたリスト
 */
// H=list.shift([], Return) :- H=[], Return=nil.
// H=list.shift('.'(Value, Next), Return) :- H=Next, Return=Value.

/**
 * list.append(+List1, +List2, -Res)
 *
 * Appends List1 and List2 and binds the result to Res
 */
H=list.append([], B) :- H=B.
H=list.append([Value|Next], B) :- H=[Value|list.append(Next, B)].


/**
 * list.of_queue(+Queue, -List)
 * 
 * Converts Queue to a list and binds the result to List.
 * @see queue
 */
H=list.of_queue(queue.new(Head, Head)) :- H=[].
H=list.of_queue(queue.new(Head, Tail)) :-
	H=[El | list.of_queue(list.shift(queue.new(Head, Tail), El))].


/**
 * list.grep(+F, +List, -Res):
 *
 * リストListの要素のうちFによってtrueが返るもののみを含むリストをResに返します。
 * @example r=list.grep(f, [1,2,3,4,5]).
 *          H=[f,N] :- N<3 | H=[true, N].
 *          H=[f,N] :- N>=3 | H=[false,N].
 */
H=list.grep(F, List) :- unary(F) | H=list.grep_s0(list.map(F, List)).
H=list.grep_s0([ [true, El] | CDR ]) :- H=[El | list.grep_s0(CDR)].
H=list.grep_s0([ [false, El] | CDR ]) :- H=list.grep_s0(CDR), nil(El).
H=list.grep_s0([]) :- H=[].

/**
 * list.map(+F, +List, -Res):
 *
 * FとリストListの各要素との2要素リストからなるリストをResに返します。
 * H=list.map(F, [B1, ..., Bn]) は H=[[F, B1], [F, B2], ..., [F, Bn]]です。
 */
H=list.map(F, List) :- H=list.fold(F, [], List).

/*
 * list.fold(+F, +I, +List, -Res):
 * 
 * H=list.fold(F, I, [B1, ..., Bn]) は H=[[F, B1], [F, B2], ..., [F, Bn]|I] です。
 * @example r=list.fold("+", 0, [1,2,3]). (H=[ ["+",A]|B] :- A+B=C | H=C).
 */
//H=list.fold(F, I, []) :- unary(F), unary(I) | H=I.
//H=list.fold(F, I, [CAR|CDR]) :- unary(F), unary(I) | H=[ [F, CAR] | list.fold(F, I, CDR)].

/*
 * list.unfold
 * 
 * (Seed -> Boolean)
 *  -> (Seed -> Value)
 *  -> (Seed -> NewSeed)
 *  -> Seed
 *  -> (Seed -> TailValue)
 *  -> List
 * 
 * @example
 * r=list.unfold(p,f,g,0,f).
 * H=[p,N]:-10>N|H=true.
 * H=[p,N]:-N=10|H=false.
 * H=[g,N]:-M=N+1|H=M.
 * H=[f,N]:-H=N.
 * ==> r([0,1,2,3,4,5,6,7,8,9,10,11])
 * @see Gauche http://www.shiro.dreamhost.com/scheme/gauche/man/gauche-refj_216.html#SEC239
 */
//H=list.unfold(P, F, G, Seed, Tailgen) :-
//	unary(P),unary(F),unary(G),unary(Seed),unary(Tailgen) |
//	H=list.unfold_s0(P, F, G, Seed, Tailgen, [P,Seed]).
//H=list.unfold_s0(P, F, G, Seed, Tailgen, true) :-
//	unary(P),unary(F),unary(G),unary(Seed),unary(Tailgen) |
//	H=[ [F,Seed] | list.unfold_s0(P, F, G, [G,Seed], Tailgen, [P,Seed]) ].
//H=list.unfold_s0(P, F, G, Seed, Tailgen, false) :-
//	unary(P),unary(F),unary(G),unary(Seed),unary(Tailgen) |
//	H=[ [F,Seed] ].

/**
 * list.flatten(+List, -Res)
 *
 * @example
 *  r=list.flatten([0,[a,b,c],[["a",["b"],["c","d"]]]])
 *    ==>
 *  r=list.flatten([0,a,b,c,"a","b","c","d"])
 */
H=list.flatten([]) :- H=[].
H=list.flatten([CAR|CDR]) :- unary(CAR) | H=[CAR|list.flatten(CDR)].
H=list.flatten([[CAR|CADR]|CDR]) :- H=list.flatten([CAR|list.append(CADR,CDR)]).
//Res=list.flatten(nil, R) :- Res=R.
//Res=list.flatten(int(N), R) :- Res=cons(int(N), R).
//Res=list.flatten(cons(A, B), R) :- Res=list.flatten(A, list.flatten(B, R)).

/**
 * list.choose_k(+List, +K, -Res)
 *
 * Generates a list of all ways of choosing K elements from List and binds it to Res.
 *
 * @example
 * r=choose_k([a, b, c, d, e], 3).
 * r=choose_k([b, c], 1).
 */
H=list.choose_k(L, K) :- ground(L), K=0 | H=[[]].
H=list.choose_k([], K) :- int(K), K=\=0 | H=[].
// Hd を選ぶ場合とそうでない場合の全組み合わせをくっつける 
H=list.choose_k([Hd|Tl], K) :- int(K), ground(Tl) |
    H=list.append(list.dist(Hd, list.choose_k(Tl, K-1)), list.choose_k(Tl, K)).

// map (cons A) L
H=list.dist(A, []) :- ground(A) | H=[].
H=list.dist(A, [Hd|Tl]) :- ground(A) | H=[[A|Hd]|list.dist(A, Tl)].

/*
 * list.uniq
 * 
 * List -> List
 * 
 * uniq でないことが書けないので膜の反応終了を条件に not の動作をさせるようにした。
 */
//H=list.uniq(L) :- ground(L) | H={r=list.uniq0(L)}.
//H=list.uniq0([]) :- H=[], fin.
//H={fin, r=R, $p[], @r} :- ground(R) | H=R.
//H=list.uniq0([Hd|Tl]) :- uniq(Hd) | H=[Hd|list.uniq0(Tl)].
//H={HH=list.uniq0([Hd|Tl]), $p[HH,Tl], @r}/ :- ground(Hd) | H={HH=list.uniq0(Tl), $p[HH,Tl], @r}.

/*
 * list.uniq
 * 
 * List -> List
 * 
 * not_uniq を追加したのでこう書ける
 * 現状、uniq() の履歴が共有されてしまう。
 */
// H=list.uniq([     ]) :-                H=[                ].
// H=list.uniq([Hd|Tl]) :-     uniq(Hd) | H=[Hd|list.uniq(Tl)].
// H=list.uniq([Hd|Tl]) :- not_uniq(Hd) | H=    list.uniq(Tl) .


/**
 * list.split(+List, +N, -Tail, -Head)
 *
 * Trims List after the first N element and binds it to Head and the rest to Tail.
 * 2006.2.28 by inui
 */
H=list.split(List,  X, Tail) :- X=0    | H=[], Tail=List.
H=list.split([   ], X, Tail) :- int(X) | H=[], Tail=[].
H=list.split([Y|Z], X, Tail) :- X>0    | H=[Y|list.split(Z,X-1,Tail)].

/**
 *  list.length(List, Len, NewList)
 *  
 *  Bind the length of List to Len
 *  2006/06/07 Sasaki
 */
H=list.length([Head|Tail], Len) :- H=[Head|list.length(Tail,Len1)], Len=Len1+1.
H=list.length([],Len) :- H=[], Len=0.

/**
 *  list.update(List, N, X, NewList, Old)
 *
 *  ListのN番目(N=0,1,2,...)の要素を新要素Xで置換し、置換対象となった要素Oldを返します。
 *  ただし、N > list.length(List) の場合は置換は行わず、Xをそのまま返します。
 *  2006/06/07 佐々木
 */
H=list.update([], N, X, Ls) :- N>0 | H=X, Ls=[].
H=list.update([Head|Tail], N, X, Ls) :- N=0 | H=Head, Ls=[X|Tail].
H=list.update([Head|Tail], N, X, Ls) :- N>0 | H=list.update(Tail,N-1,X,Ls1), Ls=[Head|Ls1].

/**
 *  list.get(List, N, Got, NewList)
 *
 *  ListのN番目(N=0,1,2,...)の要素を参照し、Gotとして返します。
 *  もとのListからGotを取り除いたものを、NewListとして返します。
 *  2006/06/07 佐々木
 */
H=list.get([Head|Tail], N, Got) :- N=0 | Got=Head, H=Tail.
H=list.get([Head|Tail], N, Got) :- N>0 | H=[Head|list.get(Tail,N-1,Got)].

/**
 * list.set(+List, +N, +New, -Old, -NewList)
 *
 * List の N 番目(N=0,1,2,...)の要素に New をセットしたリストを返します．
 * 元々あった要素は Old に返します．
 * List が空だったり，リストの長さを超えてセットしようとした場合は
 * リストは変更されず，セットしようとした要素は Old に 返ります．
 * 2006/09/23 inui
 */
H=list.set([], N, New, Old) :- int(N) | H=[], Old=New.
H=list.set([Head|Tail], N, New, Old) :- N = 0 | H=[New|Tail], Old=Head.
H=list.set([Head|Tail], N, New, Old) :- N > 0 | H=[Head|list.set(Tail,N-1,New,Old)].

/**
 * list.reverse(+List, -ReversedList)
 *
 * Reverse List and binds it to ReversedList.
 * 2006/07/05 inui
 */
H=list.reverse(List) :- H=list.reverse(List, []).
H=list.reverse([], List) :- H=List.
H=list.reverse([Car|Cdr], List) :- H=list.reverse(Cdr, [Car|List]).

}.
//res = list.flatten(cons(cons(int(1),cons(int(2),int(3))), int(4)), nil).
