Blogged by Ujihisa. Standard methods of programming and thoughts including Clojure, Vim, LLVM, Haskell, Ruby and Mathematics written by a Japanese programmer. github/ujihisa

Sunday, October 21, 2012

I'll be in Japan and Taiwan for a while

  • Taiwan: Oct 28
  • Japan: Oct 28 to Nov 21
  • Taiwan: Nov 21 to Nov 23

I have no particular plans in Taiwan yet besides having awesome 小籠包s there.

小籠包 from wikipedia

小籠包 from wikipedia

Whereas I have plans in Japan -- I'll be organizing 4 conferences/meetups there.

If you are interested in either some of the topics above or me, and have plan to visit Kanto or Kansai area, you should check it out and give a presentation there.

Saturday, October 13, 2012

Mergesort in Haskell, Clojure and Scheme

In Haskell

Mergesort requires O(1) index access so I used Data.Vector instead of List.

import qualified Data.Vector as V

-- length (sort2 x y) == 2
-- sorted (sort2 x y) is true
sort2 :: Ord a => a -> a -> V.Vector a
sort2 x y = if x < y then V.fromList [x, y] else V.fromList [y, x]

-- contract: sorted xs && sorted ys
-- length (merge xs ys) == length xs + length ys
-- sorted (merge xs ys) is true
merge :: Ord a => V.Vector a -> V.Vector a -> V.Vector a
merge xs ys = case (xs V.!? 0, ys V.!? 0) of
  (Nothing, _) -> ys
  (_, Nothing) -> xs
  (Just x, Just y) -> if x < y
    then x `V.cons` merge (V.tail xs) ys
    else y `V.cons` merge xs (V.tail ys)

-- length (mergeSort xs) == length xs
-- sorted (mergeSort xs) is true
mergeSort' :: Ord a => V.Vector a -> V.Vector a
mergeSort' xs = case V.length xs of
  0 -> xs
  1 -> xs
  2 -> sort2 (V.head xs) (V.last xs)
  otherwise -> let (a, b) = split2 xs in
               merge (mergeSort' a) (mergeSort' b)

mergeSort :: Ord a => [a] -> [a]
mergeSort = V.toList . mergeSort' . V.fromList


-- contract: length xs > 2
-- (a, b) = split2 xs => length a + length b == length xs
split2 :: Ord a => V.Vector a -> (V.Vector a, V.Vector a)
split2 xs = (V.take (V.length xs `div` 2) xs, V.drop (V.length xs `div` 2) xs)

main = do
  print $ mergeSort [3, 1, 4, 1, 5, 9, 2]

In Clojure

(defn sort2 [x y]
  (if (< x y) [x y] [y x]))

(defn merge2 [xs ys]
  (cond
    (empty? xs) ys
    (empty? ys) xs
    :else
    (let [x (first xs) y (first ys)]
      (if (< x y)
        (cons x (merge2 (rest xs) ys))
        (cons y (merge2 (rest ys) xs))))))

(defn merge-sort [xs]
  (cond
    (> 2 (count xs)) xs
    (= 2 (count xs)) (apply sort2 xs)
    :else (let [[a b] (split-at (/ (count xs) 2) xs)]
            (merge2 (merge-sort a) (merge-sort b)))))

(prn (merge-sort [3 1 4 1 5 9 2]))

Scheme (Gauche)

With List (slow)

(use srfi-1)

(define (sort2 x y)
  (if (< x y) (list x y) (list y x)))

(define (nil? xs)
  (eq? xs '()))

(define (merge2 xs ys)
  (cond
    ((nil? xs) ys)
    ((nil? ys) xs)
    ((let ((x (car xs))
           (y (car ys)))
       (if (< x y)
         (cons x (merge2 (cdr xs) ys))
         (cons y (merge2 xs (cdr ys))))))))

(define (merge-sort xs)
  (cond
    ((> 2 (length xs)) xs)
    ((= 2 (length xs)) (apply sort2 xs))
    ((receive (a b) (split-at xs (/ (length xs) 2))
       (merge2 (merge-sort a) (merge-sort b))))))

(print (merge-sort '(3 1 4 1 5 9 2 6)))

With Vector (fast)

(use srfi-43)

(define (sort2 x y)
  (if (< x y) (vector x y) (vector y x)))

(define (merge2 xs ys)
  (cond
    ((vector-empty? xs) ys)
    ((vector-empty? ys) xs)
    ((let ((x (~ xs 0))
           (y (~ ys 0)))
       (if (< x y)
         (vector-append (vector x) (merge2 (vector-copy xs 1 -1) ys))
         (vector-append (vector y) (merge2 xs (vector-copy ys 1 -1))))))))

(define (merge-sort xs)
  (cond
    ((> 2 (vector-length xs)) xs)
    ((= 2 (vector-length xs)) (sort2 (~ xs 0) (~ xs 1)))
    ((let ((a (vector-copy xs 0 (div (vector-length xs) 2)))
           (b (vector-copy xs (div (vector-length xs) 2) -1)))
       (merge2 (merge-sort a) (merge-sort b))))))

(print (merge-sort #(3 1 4 1 5 9 2 6)))

Followers