--
-- This file has been auto-generated by egison-translator.
--

def doubleList $a :=
  matcher
    | cons $ $ as ((a, a), doubleList a) with
      | (xs, ys) ->
        matchAll (xs, ys) as (list a, list a) with
          | ($x :: $rs1, $y :: $rs2) -> ((x, y), (rs1, rs2))
    | join $ $ as ((list a, list a), doubleList a) with
      | (xs, ys) ->
        matchAll (xs, ys) as (list a, list a) with
          | ($hs1 ++ $ts1, $hs2 ++ $ts2) -> ((hs1, hs2), (ts1, ts2))
    | ccons $ $ as (a, doubleList a) with
      | (xs, ys) ->
        matchAll (xs, ys) as (list a, list a) with
          | ($x :: $rs1, #x :: $rs2) -> (x, (rs1, rs2))
    | $ as something with
      | tgt -> [tgt]

def lcs $xs $ys :=
  matchAll (unpack "thisisatest", unpack "testing123testing") as
    doubleList char with
    | loop $i (1, $n)
        (_ ++ ccons $c_i ...)
        _ -> (n, pack (map (\$i -> c_i) (between 1 n)))

-- Local sortBy function for custom comparison
def sortBy f xs :=
  match xs as list something with
    | [] -> []
    | $x :: [] -> [x]
    | _ ->
      let n := length xs
          p := nth (quotient n 2) xs
          (ys1, ys2, ys3) := splitByOrderingBy f p xs
       in sortBy f ys1 ++ ys2 ++ sortBy f ys3
       
def splitByOrderingBy f p xs :=
  match xs as list something with
    | [] -> ([], [], [])
    | $x :: $rs ->
      let (ys1, ys2, ys3) := splitByOrderingBy f p rs
       in match f x p as ordering with
            | less -> (x :: ys1, ys2, ys3)
            | equal -> (ys1, x :: ys2, ys3)
            | greater -> (ys1, ys2, x :: ys3)

sortBy 2#(compare (2#$1 $1) (2#$1 $2)) (lcs "thisisatest" "testing123testing")