неділю, 4 серпня 2013 р.

NoCopyPaste Paranoid

Напишу ка я идеальный NoCopyPaste Quicksort на Haskell.

NoCopyPaste — это один из принципов идеального кода. Суть проста и всем знакома: если в коде появляется два одинаковых выражения, их нужно вынести в отдельную функцию (метод, модуль, объект), и использовать оттуда, иначе — копипаст.

Но иногда бывает очень трудно понять, что нужно вынести, а что оставить. Формально эту трудность можно выразить примерно так: "Какого минимального размера выражение нужно выносить в отдельную функцию?".

Как можно так жить?

У нас на проекте много кода на Python. Это не основной язык, и используется только для инфраструктурных решений (и поэтому никаких тестов), но все равно его много. Python очень динамически типизирован. Большая проблема это имена, они не проверяются на этапе компиляции. Часто при рефакторинге или даже обыденном программировании встречаются ошибки в именах, которые могут быть фатальными. И чем чаще повторяется одно и тоже имя (слово) в коде тем больше вероятность где-то написать его неправильно.

Поэтому для Python минимальное выражение которое нужно выносить — это одно (!!!) слово. Звучит странно, так как обычно выносимый код заменяется одной функцией. И поэтому нет смысла выносить отдельные имена, так как все равно они заменятся на... имена. Так я стал параноиком. Но все таки в коде близко друг к другу два одинаковых слова сигнализируют о потенциальных проблемах. (Тут нужно понимать также, что определение не считается. То есть слова могут встречаться в основном два раза: в определении и в использовании.)

Haskell

На Haskell это не так страшно как на Python, но... Берем обычный Quicksort.

qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort (filter (<x) xs) ++ [x] ++ qsort (filter (>=x) xs)

Сколько раз повторяются слова? Видимо много. Плюс фильтр отрабатывает дважды. Используем partition.

qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = let (l, g) = partition (<x) xs
               in qsort l ++ [x] ++ qsort g

Но внимательный глаз заметит еще и два вхождения qsort в let-выражении. Исправляем.

qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = uncurry (on concat qsort) (partition (<x) xs)
    where
      concat l g = l ++ [x] ++ g

Что еще? Правильно, конкатенация (++) в определении concat встречается дважды. Вообще-то часто библиотечная функция concat не подходит, а хочется иметь например:

concat2 :: [a] -> [a] -> [a]
concat3 :: [a] -> [a] -> [a] -> [a]

Ну что же, не проблема. Сделаем concat со статическим (compile time) числом аргументов (может такое уже где-то есть?):

class StaticConcat a b where
    sconcat :: a -> b

instance (a ~ b) => StaticConcat [a] [b] where
    sconcat = id

instance (StaticConcat [b] c, a ~ b) => StaticConcat [a] ([b] -> c) where
    sconcat a b = sconcat (a ++ b)

(Конечно еще можно было бы обобщить sconcat например на моноид, но это уже к сортировке не относится.) Используя sconcat конечная сортировка выглядит довольно безкопипастно.

qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = uncurry (on (`sconcat` [x]) qsort) (partition (<x) xs)

Послесловие

Чем больше копипасты в коде, тем меньше энтропии, то есть больше предсказуемости, больше фона, воды; не видна суть. Мы ведь не мартышки, повторять одно и тоже? Сделаем каждый модуль неповторимым! Увеличим энтропию нашых функций! Скажем "нет" копипасте!

Немає коментарів:

Дописати коментар