# Summary of Week 1 - Implementing nub

summary-week-1.md

Summary of Week 1 - Implementing nub

• 14 位參與者
• 18 種解法（外加一種使用 Prolog XD）
• 大部分時間複雜度為 O(n²)，少數運用 Int 的 Ord 或 Hashable 性質將複雜度壓到 O(nlog n) 甚至 O(n)
• 大部分實作是 stable 的（在這裡定義為保持輸入資料從前面往後枚舉的順序）
  • 多數利用 foldr 搭配 reverse
  • 少部分利用 zip 維護資料順序

Solutions

1. 王韋勝 https://gist.github.com/wilson8507/f81f2eb0e63824e1a8e8fc42f4dd1cc4

• 時間複雜度皆為 O(n²)
• nub3 是 stable 的

nub1 :: [Int] -> [Int]
nub1 xs = foldr isntElement [] xs
  where isntElement x xs | length [y | y <- xs, y == x] == 0 = x:xs
                         | otherwise = xs

nub2 :: [Int] -> [Int]
nub2 [] = []
nub2 (x:xs) | length [y | y <- nub2 xs , y == x] /= 0 = nub2 xs
            | otherwise = x : nub2 xs

nub3 :: [Int] -> [Int]
nub3 [] = []
nub3 (x:xs) = x : nub3 (filter (/= x) xs)

2. Tai An Su https://gist.github.com/taiansu/3c041a7b972701c4154e651b4bcc4693

• 時間複雜度皆為 O(n²)

nub' :: [Int] -> [Int]
nub' = foldr f [] where
  f x xs
    | x `elem` xs = xs
    | otherwise   = x:xs

-- without using `elem`
nub'' :: [Int] -> [Int]
nub'' = foldr f [] where
 f x xs
  | length (filter (x ==) xs) > 0 = xs
  | otherwise                     = x:xs

3. 葉柏宏 https://gist.github.com/rareone/cd7db3d7ac4a4fbadd48d1b4ab472f1a

• 時間複雜度為 O(nlog n)
• 運用 Int 可比較大小的性質（Ord）

qsnub [] = []
qsnub (a:xs) = compo (<a) xs ++ [a] ++ compo (>a) xs
  where compo f = qsnub. filter f

4. 潘廣霖 https://gist.github.com/andy0130tw/528bec01bbfff96a1244c46c61d9db00

• 時間複雜度為 O(n²)
• nub 是 stable 的

nub' :: [Int] -> [Int] -> [Int]

nub' rs []     = reverse rs
nub' rs (x:xs) | elem x rs = nub'    rs  xs
               | otherwise = nub' (x:rs) xs

nub :: [Int] -> [Int]

nub = nub' []

{-
some test cases:
  * nub [] == []
  * nub [1, 2, 3, 4] == [1, 2, 3, 4]
  * nub [1, 1, 1, 2] == [1, 2]
  * nub [1, 2, 2, 5, 3, 5] == [1, 2, 5, 3]
  * nub [1, 2, 3, 4, 2, 3, 1, 5, 4, 3] == [1, 2, 3, 4, 5]
-}

5. Shin-Cheng Mu https://gist.github.com/scmu/900cc6b30972d2b55bf9cfc8803d8c3c

• 時間複雜度皆為 O(nlog n)
• 運用 Int 可比較大小的性質（Ord）
• nubStable 是 stable 的

import Data.Ord
import Data.List

nubSimple :: [Int] -> [Int]
nubSimple = map head . group . sort

nubStable :: [Int] -> [Int]
nubStable = map fst . sortBy (comparing snd). map head .
              groupBy ((. fst).(==).fst) . sort . flip zip [0..]

6. 郭宗霆 https://gist.github.com/jc99kuo/05d0728b3b479465b0b1d62fa7c03aeb

• 時間複雜度為 O(n²)
• nub 是 stable 的

--  FLOLAC 2018 Week 1 -- nub: filter out duplicating integers on a list

nub :: [Int] -> [Int]

nub ix = dedup [] ix
  where
    dedup = \xs ys ->
      case ys of
        [] -> xs
        (yhead:ytail) ->
           if (elem yhead xs) then
             dedup xs ytail
           else
             dedup (xs ++ [yhead]) ytail

7. 江宗儒 https://gist.github.com/ray851107/afc8c9c82a56403667e3896e7b0cde4d

• 時間複雜度為 O(n²)
• nub 是 stable 的

import Data.List

nub xs = [ x | (x, p) <- zip xs (inits xs), x `notElem` p]

8. 陳昱維 https://gist.github.com/akira02/1ae4c0cce5d3941bce00813fcca4bbd1

• 時間複雜度為 O(nlog n)
• 運用 Int 可比較大小的性質（Ord）
• 偷用別人寫好的 Data.Set XD
• nub 是 stable 的

import qualified Data.Set as S

nub = go S.empty
  where go _ [] = []
        go s (x:xs) | S.member x s = go s xs
                    | otherwise    = x : go (S.insert x s) xs

9. Terry Cheong https://gist.github.com/terry182/3f31de2b19c66db208d84afafa539ec9

• 時間複雜度為 O(n²)
• nub 是 stable 的

nub' :: [Int] -> [Int]
nub' (x:xs) | elem x xs = nub' xs
            | otherwise = x:(nub' xs)
nub' [] = []

nub = reverse . nub' . reverse

10. 許恆與 https://gist.github.com/m80126colin/0852fa76bf741c4a258840f892033aae

• 時間複雜度為 O(n) 或者 O(nlog n) （端看實作，在舊版 unordered-containers 的 HashSet.insert 曾經是 O(min(n,W))，現在改為 O(log n)）
• 運用 Int 是 Hashable 的性質
• 有一定機率會把東西變不見
• nub 是 stable 的

import Data.Hashable
import Data.HashSet

-- Amortised linear-time by hashing
uniqhs :: (Hashable a, Eq a) => HashSet a -> [a] -> [a]
uniqhs _ []     = []
uniqhs h (x:xs) = if member x h then uniqhs h xs else x:uniqhs (insert x h) xs

nub :: [Int] -> [Int]
nub = uniqhs empty

11. Jensen Holder https://gist.github.com/shhyou/cffcaafe0fe6bb410a60a0f8aaf44701

• 時間複雜度為 O(n²)
• nub 是 stable 的

bun []                   = []
bun (x:xs) | x `elem` xs =     bun xs
           | otherwise   = x : bun xs

nub :: Eq a => [a] -> [a]
nub = reverse . bun . reverse

• 出來面對啦!! XD

append3(XS, YS, ZS, OS) :- append(XS, WS, OS), append(YS, ZS, WS).

% nub(PS ++ (Q:QS) ++ (Q:RS)) = nub(PS ++ (Q:QS) ++ RS)
nub(XS, OS) :- append3(PS, [Q|QS], [Q|RS], XS), !,
               append3(PS, [Q|QS], RS, YS),
               nub(YS, OS).
nub(XS, XS).

12. Yu-Ren Pan https://gist.github.com/YuRen-tw/9c24e474f8ab46f5d1edba2b46be0904

• 時間複雜度為 O(n²)
• nub 是 stable 的

nub :: [Int] -> [Int]
nub [] = []
nub (x:xs) = x:(nub $ filter (/= x) xs)

13. 林子期 https://gist.github.com/Zekt/7eaefa0f142b20569664a8460fd5da81

• 時間複雜度為 O(n²)
• nub 是 stable 的

import Data.List
nub xs = map fst . filter (uncurry notElem) $ zip xs (inits xs)

14. 洪崇凱 https://gist.github.com/RedBug312/ed954151416c3293f271d0e6f46e5494

• 時間複雜度為 O(n²)

nub :: [Int] -> [Int]
nub []     = []
nub [x]    = [x]
nub (x:xs) = if x `elem` xs then nub xs else x : nub xs