Dmitry Popov

(сам внезапно набирающий популярность ответ здесь)

Дамы и господа! Не проходите мимо! Только сегодня в нашем бродячем цирке великий йог и аскет Лямбдагарбха продемонстрирует уникальный фокус материализации! Имея полиморфную функцию, оперирующую произвольными типами (полифорфными, не конкретными), функциями из них и туплами, только зная ее тип и умея ее вызывать, он материализует ее исходник, даже если она скомпилирована в другом городе, и никакое ее оригинальное представление уже не доступно.

Выглядит это так. Допустим, мы в отдельно компилируемом модуле описываем такую функцию:

some_fun :: (a, (b, c)) -> (b -> b) -> (b -> a) -> ((b, a), c)
some_fun (a,(b,c)) f g = ((f . f $ b, g . f $ b), c)

В ней не упоминаются числа, строки и другие конкретные типы, но есть пары и функции. Теперь мы в другом модуле пишем

term = reify ... some_fun
result :: String
result = view term

И получаем в result строку
"(\x1 -> (\x2 -> (\x3 -> (((x2 (x2 (fst (snd x1)))), (x3 (x2 (fst (snd x1))))), (snd (snd x1))))))"
которая правдиво воспроизводит внутреннее устройство some_fun, только без имен переменных и синтаксического сахара. В частности, видно, что второй аргумент действительно применяется нужное число раз, из одного только типа это вывести невозможно, это не djinn, который из типа простейшую реализацию изобретает, тут действительно переданная функция материализуется.

Как это работает и что должно быть там вместо троеточия?( Read more... )

Сперва пример. Вот такая программа на хаскеле вычисляет и выводит ответ на жизнь, вселенную и вообще:

import Control.Applicative
main = print $ answer succ 0  where
  one = pure <*> (pure :: a -> b -> a)
  inc = (<*>) ((<*>) <$> pure)
  mul = (<*>) <$> pure
  h = mul <*> inc
  answer = h . h . h $ one

Аппликативный функтор характеризуется наличием двух функций с определенными свойствами:

class Functor f => Applicative f where  
  pure :: a -> f a                   -- Lift a value.  
  (<*>) :: f (a -> b) -> f a -> f b  -- Sequential application.

Фишка в том, что для ((->) a) эти две функции - комбинаторы K и S!

instance Applicative ((->) a) where
  pure = const     -- \x . \y . x
  (<*>) f g x = f x (g x)

А мы знаем, что через S и K можно выразить любую лямбда-функцию, а значит и любую вычислимую функцию. Возьмем, например, функцию
h(x) = x * (x + 1)
Она интересна тем, что использует только умножение и инкремент, и будучи трижды применена к единице, дает 42. Для арифметики на лямбдах задействуем числа Черча. Число n там представляется функцией, которая берет другую функцию и ее аргумент, и применяет ту функцию n раз. Так, единица применяет данную функцию f один раз:
one f x = f x
Чтобы увеличить n на 1, нужно применить f на один раз больше, чем это делает n:
inc n f x = f (n f x)
Умножение a на b делается применением b a раз:
mul a b f x = a (b f) x
(x тут можно "сократить" и не писать)
Тогда h будет выглядеть как
h x = mul x (inc x)

Теперь возьмем комбинаторный базис:
S x y z = (x z) (y z)
K x y = x
Пользуясь простым алгоритмом конверсии, наши арифметические функции можно выразить через S и K:
one = S K K
inc = S (S (K S) K)
mul = S (K S) K
h = S mul inc

Теперь осталось лишь вспомнить, что K = pure, S = <*>, а
pure x <*> y = x <$> y
Подставив их вместо S и K, получим программу выше.
Представляете, какие открываются горизонты? Я тоже нет. Разве что обфускатор можно написать. :)

Помня о том, какое бурление вызвало сравнение скорости Лиспа с другими языками в прошлом номере ПФП, прошу помощи зала не допустить несправедливости. Я сейчас доделываю сравнение скорости разных методов парсинга, сделал вариант на Хаскеле на базе Parsec2, и получившаяся скорость мне совсем не нравится. До этого на Хаскеле не писал, поэтому наверняка мог сильно налажать. Исходник (~70 строк) выложил здесь.
Суть программы - чтение карты формата OpenStreetMap и вычисление ее реальных границ - минимальных и максимальных значений широты и долготы встреченных точек. Собирал ее с GHC 6.8.3 и 6.10.1, Parsec 2.1.0.1, команда для сборки:

ghc -O2 -package parsec bounds.hs -o bounds

Сейчас скорость получается около 3 МБ/с.
Пример простой карты тут. Скорость тестировал на карте Сингапура (архив 1.2 МБ).

Прошу более опытных товарищей глянуть на исходник и указать на явные косяки. Можно ли заметно ускорить программу без сильных изменений описанной там грамматики?

Некоторые люди любят сравнивать популярность разных языков, технологий и пр. по числу запросов в поисковиках и постов в блогах. В прошлом году попался мне в руки лог поисковика AOL за весну 2006 года, содержащий 36 миллионов записей с примерно 21 миллионом различных запросов от 657 тысяч пользователей. Сделал я тогда себе (на Окамле, разумеется) анализатор этих данных, который по любому слову или набору слов выдает отсортированные по популярности содержащие их запросы. И обнаружил много интересного. В частности, там было 84 разных запроса со словом Haskell, но знаете, сколько из них относилось к языку программирования? Примерно ноль. Самые популярные - haskell texas, colleen haskell, haskell college. Остальные - ( Read more... )
Выводы:
1. Будете делать язык программирования, не называйте его человеческим именем!
2. Сравнивать популярность по числу поисков и блогов чревато ошибками.

P.S. А знаете, что в России самое интересное для американцев?
( Read more... )