実用的でないsort

sort.egins

-- Egison Version >= 3.10.0
-- $ egison -N
-- > loadFile "sort.egins"



--
-- Utils
--

sorted'? xa n y :=
  let xb := map (\i -> xa_i) [1..n]
  in sorted? (append xb [y])

sorted? :=
  \match as list integer with
    | []                    -> True
    | _   :: []             -> True
    | $x1 :: ?(x1 >) :: _   -> False
    | _   :: $x2     :: $xs -> sorted? (cons x2 xs)



--
-- Codes
--

sort :=
  \match as multiset integer with
    | loop $i (1, $n) ($xa_i :: ...)
                      ((?(\y2 -> sorted'? xa n y2) & $y) :: [])
        -> append xb [y]
    where
      xb := map (\i -> xa_i) [1..n]



--
-- Tests
--
-- $ egison -N -t sort.egins

assertEqual "sort1"
  (sort [7,6,9,8,6])
  [6, 6, 7, 8, 9]

assertEqual "sort2" -- 2min
  (sort [7,2,6,3,4,1,5])
  [1..7]

--assertEqual "sort3やめとこう"
--  (sort [39,34,55,29,14,57,13,28,100,48,20,8,5,18,47,15,93,87,9,82,89,10,45,25,44,22,67,79,80,51,23,58,35,19,83,2,37,53,43,88,64,6,50,95,49,27,77,63,69,1,92,31,61,90,86,24,91,84,40,78,74,11,71,98,76,30,3,56,75,62,85,68,32,81,73,36,72,38,60,4,33,54,94,16,12,42,99,7,66,46,41,26,59,97,21,70,96,17,65,52])
--  [1..100]