November 1st, 2009

with Cat The Cat

Умение программировать.

В дополнение к моему комментарию на RSDN.

Некоторые товарищи считают, что "умение программировать не зависит от парадигмы".

Собственно, Хаскелем я пользуюсь более 10 лет, и где-то лет 8 участвую в спорах на тему "функциональное программирование против всего остального программирования". За это время я повидал много всякого. В частности, что люди, считающие себя умеющими программировать не могут воспринять что-либо, выходящее за рамки привычного императивного стиля. В личном общении это передаётся фразой "А что, если мне здесь лог понадобится, это что, тянуть параметры или тип менять?", которая дополняется нарочито вытянутым лицом и дебиловато отвисшей челюстью.

Моё мнение таково: от парадигмы не зависит умение выражать свои мысли. Это у кого-то из великих было насчёт "программист должен уметь владеть, прежде всего, своим родным языком".

Задачи в программировании, обычно, комбинационные. "Компонентные", как принято сейчас говорить. Надо взять то-то и то-то, скомбинировать с тем-то и тем-то и получить то, что нужно. Поэтому, накопив 108000 повторений1 примерно одинаковых действий человек становится весьма опытным. Он может выразить что угодно небольшим количеством приёмов. "Писать символьные вычисления надо на Фортране или ассемблере", если цитировать "Настоящие программисты не используют Паскаль".

Я почему и отделил умение выражать мысли от умения программировать - уметь программировать можно, причём на вполне определённом языке. Особенно на вполне определённом языке. Многие с этим справляются, лет за пять-шесть нарабатывают технику. А вот выражать свои мысли вообще тяжелее, здесь нужно учитывать логику текущего инструмента. Логики разные, и знание парочки можно сравнить со знанием русского и японского языков. Или русского и Фортрана. ;)


1Столько требуется для изучения формы в у-шу, считается. Это не такая уж и большая цифра: если на форму требуется 5 минут вместе с отдыхом, то при ежедневной практике в 8 часов 365 дней в году на 108000 повторений формы потребуется три года. А испытание того или иного приёма в программировании занимает гораздо меньше времени - десятки секунд.
with Cat The Cat

Про представления метриц в ФЯ.

Самое простое: матрица - это вектор-столбец векторов-строк. С этим представлением знакомы все, оно всем привычно. Вектор определяется, как пустой вектор и как соединение головного элемента и вектора-хвоста.

Можно придумать и другие рекурсивные определения.

Например, такое:
data DiagDecomposed a =
        DiagEmpty
    |   Diagonal
            [a] -- column a_{{2..n}1}
            a   -- element a_{11}
            [a] -- row a_{1{2..m}}
            (DiagDecomposed a)
Мне про него рассказал Рома Салмин rsalmin.

Матрица разбивается на четыре части:
   a  rrrrr

    c  mmmmm
    c  mmmmm
    c  mmmmm
Ведущий элемент a, остаток строки rrrrr, остаток столбца ccc и остаток матрицы mmm...mmm.

Это упрощённый вариант иерархического разбиения в стиле алгоритмов, независящих от размера кэша.

Такое разбиение задаётся вот так:
data COMatrix a =
        COCol [a]
    |   CORow [a]
    |   CODiv (COMatrix a) (COMatrix a) (COMatrix a) (COMatrix a)
Либо столбец, либо строка, либо матрица, которую делим на четыре части.

Та же метрица 4x6, что выше:
 aaa bbb
 aaa bbb

 ccc ddd
 ccc ddd
Если добавить "нулевую матрицу" (вариант COZero в определение COMatrix), то получится quadtree, что весьма неплохо, для ленточных матриц можно получить расход памяти O(NlogN).

Последнее - разреженные матрицы. Варианта два: Map (Int,Int) a и Map Int (Map Int a). Первый проще транспонировать и на этом его преимущества заканчиваются, второй проще в умножении и других операциях над матрицами, поскольку является оптимизацией самого первого варианта с вектором векторов. Здесь количество данных на матрицу всегда будет O(NlogN), где N - количество занятых элементов.

К тому же, разреженные матрицы выражены в виде достаточно простой для обработки внутри ФЯ структуры, что делает их ещё более привлекательными. ;)

Пожалуй, всё.