// fetch the first element in the list
lst.head {

    ([],[])^       :- true;
    ([:e],:e)^     :- true;
    ([:h|_],:h);
}

// fetch the last element in the list
lst.tail {

    ([],[])^        :- true;
    ([:e],:e)^      :- true;
    ([:h|:r],:l)    :- #lst.tail(:r,:l);

}

// fetch the previous to last element in the list
lst.ptail {

    ([],[])^        :- true;
    ([:e,_],:e)^    :- true;
    ([:h|:r],:l)    :- #lst.ptail(:r,:l);

}

// fetch the nth element in the list (1 to nth)
lst.item {

    ([],_,[])^          :- true;
    ([:e],1,:e)^        :- true;
    ([:h|:r],1,:h)^     :- true;
    ([:h|:r],:n,:l)     :- sub(:n,1,:m), #lst.item(:r,:m,:l);
}

// get the number of elements in a list
lst.length {

    ([],0)^     :- true;
    ([_],1)^    :- true;
    ([_|:r],:d) :- #lst.length(:r,:c), add(:c,1,:d);

}

// inverse the contents of the list
lst.flip {

    ([],[])^        :- true;
    ([:e],[:e])^    :- true;
    ([:h|:r],:l)    :- #lst.flip(:r,:l2), lst.cat(:l2,:h,:l);

}

// test if a list is a palindrome (content is the same read forward & backward, e.g. kayak)
lst.is.palindrome {

    (:l) :- lst.flip(:l,:l);

}

// flatten a list
lst.flat {

    (:i,:i)       :- !is.list(:i)^;
    ([:e],[:e])   :- !is.list(:e)^;
    ([:e],:f)     :- is.list(:e)^, #lst.flat(:e,:f);
    ([:h|:r],:l)  :- #lst.flat(:h,:hf), #lst.flat(:r,:rf), lst.cat(:hf,:rf,:l);

}

// eliminate all consecutive duplicate of items in the list
lst.zip {

    ([],[])^                :- true;
    ([:e],[:e])^            :- true;
    ([:e,:e|:r],:l)         :- #lst.zip([:e|:r],:l);
    ([:e,:f|:r],[:e|:l])    :- neq(:e,:f), #lst.zip([:f|:r],:l);

}

// pack all consecutive duplicate of items in the list into sublists
lst.pack {

    ([],[])^            :- true;
    ([:h|:r],[:h2|:l])  :- #lst.pack.transfer(:h,:r,:l2,:h2), #lst.pack(:l2,:l);
}


// transfers items into sublists
lst.pack.transfer {

    (:h,[],[],[:h]);
    (:h,[:Y|:l2],[:Y|:l2],[:h]) :- neq(:h,:Y);
    (:h,[:h|:r],:l2,[:h|:l])    :- #lst.pack.transfer(:h,:r,:l2,:l);

}

// run-length encode a list
lst.encode {

    (:li,:lo) :- #lst.pack(:li,:lp), #lst.encode.packed(:lp,:lo);

}

// run-length encode a packed list
lst.encode.packed {

    ([],[])^            :- true;
    ([:e],[:ec])^       :- #lst.encode.compress(:e,:ec);
    ([:h|:r],[:hc|:ro]) :- #lst.encode.compress(:h,:hc), #lst.encode.packed(:r,:ro);
}

// compress a list of duplicates elements by return a tuple (length, element)
lst.encode.compress {

    ([],[])^        :- true;
    (:l,[:c,:h])    :- lst.length(:l,:c), lst.head(:l,:h);

}

// run-length encode a list (but keep non-consecutive elements as they were)
lst.encode2 {

    (:li,:lo) :- #lst.pack(:li,:lp), #lst.encode2.packed(:lp,:lo);

}

// run-length encode a packed list
lst.encode2.packed {

    ([],[])^            :- true;
    ([:e],[:ec])^       :- #lst.encode2.compress(:e,:ec);
    ([:h|:r],[:hc|:ro]) :- #lst.encode2.compress(:h,:hc), #lst.encode2.packed(:r,:ro);
}

// compress a list of duplicates elements by return a tuple (length, element) if there's duplicates
lst.encode2.compress {

    ([],[])^        :- true;
    ([:e],:e)^      :- true;
    (:l,[:c,:h])    :- lst.length(:l,:c), lst.head(:l,:h);

}

// decode a run-length encoded list
lst.decode {

    ([],[])^        :- true;
    ([:e],:ed)^     :- #lst.decode.decompress(:e,:ed);
    ([:h|:r],:l)    :- #lst.decode.decompress(:h,:hd), #lst.decode(:r,:rd), lst.cat(:hd,:rd,:l);

}

// decompress a list of duplicated elements
lst.decode.decompress {

    ([],[])^            :- true;
    (:e,:e)             :- !is.list(:e)^;
    ([1,:e],:e)^        :- true;
    ([:c,:e],[:e|:r])   :- sub(:c,1,:ci), #lst.decode.decompress([:ci,:e],:r);

}

// remove every nth elements from the list
lst.drop {

    ([],_,[])^                  :- true;
    (_,1,[])^                   :- true;
    (:li,:c,:lo)^               :- #lst.drop(:li,:c,:lo,:c);

    ([],_,[],_)^                :- true;
    ([_|:r],:c,:lo,1)^          :- #lst.drop(:r,:c,:lo,:c);
    ([:h|:r],:c,[:h|:r2],:k)    :- sub(:k,1,:k1), #lst.drop(:r,:c,:r2,:k1);
}

// split a list in two given the expected number of element in the first output list
lst.split {

    ([],_,[],[])^               :- true;
    ([:e],_,[:e],[])^           :- true;
    ([:h|:r],1,[:h],:r)^        :- true;
    ([:h|:r],:c,[:h|:l1],:l2)   :- sub(:c,1,:c1), #lst.split(:r,:c1,:l1,:l2);

}

// slice a part of a list based on a starting & ending index
lst.slice {

    ([],_,_,[])^                    :- true;
    ([:h|_],1,1,[:h])^              :- true;
    ([:h|:t],1,:k?[gt(1)],[:h|:t2]) :- sub(:k,1,:k1), #lst.slice(:t,1,:k1,:t2);
    ([_|:t],:i?[gt(1)],:k,:ts)      :- sub(:i,1,:i1), sub(:k,1,:k1), #lst.slice(:t,:i1,:k1,:ts);

}

// rotate a list by n elements (left or right)
lst.rotate {

    (:l1,:n?[gte(0)],:l2)^  :- lst.length(:l1,:nl1), mod(:n,:nl1,:n1), #lst.rotate.left(:l1,:n1,:l2);
    (:l1,:n?[lt(0)],:l2)    :- lst.length(:l1,:nl1), sub(:nl1,:n,:n1), #lst.rotate(:l1,:n1,:l2);

}

// rotate a list content left by n elements
lst.rotate.left {

    (:l,0,:l)^              :- true;
    (:l1,:n?[gt(0)],:l2)    :- #lst.split(:l1,:n,:s1,:s2), lst.cat(:s2,:s1,:l2);

}