Comments 26
Решение задачи Sudoku на разных языках на rosettacode.org
P.S. Есть и на Haskell,
А насколько Функциональное программирование хорошо и почему, к примеру,, имеет смысл демонстрировать на Haskell и на такой задаче, а не, к примеру, на классическом языке Common Lisp или Clojure?
P.S. Есть и на Haskell,
Спасибо! Посмотрел. Есть довольно занятные варианты решения. Например, такой:
f x s@(h:y)=let(r,c)=divMod(length x)9;m#n=m`div`3==n`div`3;e=[0..8]in
[a|z<-['1'..'9'],h==z||h=='.'&¬Elem z(map((x++s)!!)[i*9+j|i<-e,
j<-e,i==r||j==c||i#r&&j#c]),a<-f(x++[z])y]
f x[]=[x]
main=print$f[] "53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79"На выходных буду разбираться, как это работает :).
насколько Функциональное программирование хорошо
О преимуществах ФП написано много (впрочем, как и о преимуществах ООП). Лично мне нравится: короткие функции, чистые функции, абстракции высокого уровня, декларативный стиль.
почему, к примеру,, имеет смысл демонстрировать на Haskell
Lisp, Clojure и F# - замечательные языки, но ИМХО Haskell выражает идеи ФП более "дистиллированно".
Сдаётся мне, если хочется нахлебаться от души тацитным программированием (как в приведённом обфусканном коде на хаскелле) - то лучше брать язык, где тацитное программирование поставлено во главу угла. Это APL/J/K. Там, кстати, тензоры есть из коробки, и не надо трахаться со списками списков или с пересчётом индексов в одномерном массиве списке.
Налепить судоку на джее... это, пожалуй, интересный этюд будет.
На выходных буду разбираться, как это работает :).
Функция f возвращает список всех решений. Я ничего не менял, только вынес куски кода в отдельные функции с осмысленными названиями.
f x [] = [x]
f prefix (h:suffix) = [a | z <- candidates, a <- f (prefix ++ [z]) suffix]
where
-- индексы строки и столбца текущего символа
(r,c) = divMod (length prefix) 9
-- позиции всех символов в той же строке, столбце или квадрате
positions = [i*9+j | i <- [0..8], j <- [0..8], i==r || j==c || i#r && j#c]
where
m # n = m`div`3 == n`div`3
-- все символы в той же строке, столбце или квадрате
figures = map ((prefix ++ h:suffix) !!) positions
-- допустимые символы (не встречаются в строке, столбце или квадрате)
isValid z = notElem z figures
-- кандидаты для замены текущего сивола h
-- (сам сивол h, если он цифра, или допустимая цифра, если он точка)
candidates = [x | x <- ['1'..'9'], h == x || h == '.' && isValid x]
main = print $ f [] "53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79"Извращение то ещё. Алгоритм, рассчитанный на работу с изменяемым массивом, приспособили для работы со списком. (Операция склеивания списков ++ выполняется за линейное время).
Не понял почему в последнем примере абстракция ради абстракции. Вроде бы красиво решили задачу нахождения простых чисел.
Объясните
хорошо, изменим первую строку и импортируем вымышленную функцию cached_gcd. Получится в разы быстрее.
Все ещё непонятно. Ну ладно, не буду занудой))
Да, мы можем заменить функцию сравнения (закрыв глаза на то, что нарушается фундаментальное свойство сравнения - симметричность):
primes = nubBy eq' [2..]
where
eq' a b = b `mod` a == 0Но, в рамках данного подхода (с nubBy) мы не можем прервать процесс сравнения нового числа с уже вычисленными простыми по условию b < a*a.
Не очень понял причем тут C#.
Странный план статьи, конечно. Сперва накидали каких-то кусков на сишарпе. Потом not-invented-here список на хаскелле. Потом вдруг бац, и судоку, где от двух предыдущих глав понадобилось чуть меньше, чем ничего.
Если бы вместо списка был массив, то ничего бы по существу не поменялось.
Всё равно тут делается перебор по индексам.
Ну и вместо магии "тут бежим по строке, там бежим по столбцу и транспонируем, а здесь давайте нарежем на кубики с бесконечным списком" была бы отчётливая работа по координатам.
Слишком много примитивных строительных кубиков, получается. ФП растворилось за подзадачами "ковыряться в списках". Чем это принципиально отличается от шарпа, чтобы можно было почувствовать вкус ФП? Только лаконичностью синтаксиса? Ну да, хаскелл в этом плане один из рекордсменов, тот же самый код на лиспе был бы в десять раз более пухлым, и от скобок потекли бы слёзы из глаз. Но это же вопрос синтаксиса, не более того.
А ещё в кадр краешком влезли:
цикл по условию (опа, итеративность = императивность)
ввод-вывод (IO - монада из ада!)
А ещё в кадр не влезла никакая обработка ошибок:
зацикливание
противоречивость входных данных
отсутствие решения
А ещё алгоритм предельно тупой, не умеющий решать в глубину.
Сперва накидали каких-то кусков на сишарпе. Потом not-invented-here список на хаскелле.
Код на C# - для программистов на C++/C#/Java ("классическое" ООП), незнакомых с ФП.
Самописный список - чтобы показать внутреннее устройство списка и, заодно, познакомить читателей с АТД, классами типов и операторами.
Если Вы считаете, что это было неудачное решение, то не буду спорить. Вам, как читателю, виднее. Вопрос (для статистики): у Вас есть опыт работы с АТД и/или неизменяемыми связанными списками?
ФП растворилось за подзадачами "ковыряться в списках". Чем это принципиально отличается от шарпа, чтобы можно было почувствовать вкус ФП?
Отсутствием циклов. Тем, что код близок к описанию алгоритма ("решено = все не равны нулю" и т.д.). Хотя, конечно, и на C# можно писать в функциональном стиле.
цикл по условию (опа, итеративность = императивность)
Это Вы про until? Любая не бесконечная рекурсия должна иметь условие выхода из рекурсии. А "функциональный дух" в этом случае заключается в том, что мы не используем рекурсию явно.
ввод-вывод (IO - монада из ада!)
Куда же без него! Программа, которая никак не взаимодействует с внешним миром, бесполезна.
А ещё в кадр не влезла никакая обработка ошибок:
А ещё алгоритм предельно тупой, не умеющий решать в глубину.
Это сделано намеренно, и я об этом предупредил в самом начале статьи:
"Для простоты наложим на входные данные два дополнительных условия: решение всегда есть и его можно найти без перебора."
Навернуть шаблонных типов для показа "алгебраичности" типов в "классическом ООП" это ну крайне сомнительная идея, учитывая что в итоге оно не на типах решалось и имеет сомнительный же перфоманс. Не говоря уже про старнные представления о "классическом ООП".
Ну и раз с C# начали, то что б не на F# тогда продолжить? Или как уже сами говорили - писать на C# в функциональном стиле.
Предположу, что шаблонными типами Вы называете обобщённые типы C#. В данном примере обобщённость классов не принципиальна. Суть в другом.
data Shape = Rectangle { width :: Double, height :: Double }
| Circle { radius :: Double }
deriving Show
square :: Shape -> Double
square (Rectangle w h) = w * h
square (Circle r) = pi * r * rЕсли бы меня попросили как можно ближе переписать этот код на C# в то время, когда я только начинал изучать функциональное программирование, то я бы написал так:
public abstract class Shape
{
public abstract double Square();
}
public class Rectangle : Shape
{
public double Width { get; set; }
public double Height { get; set; }
public Rectangle(double width, double height)
{
Width = width;
Height = height;
}
public override double Square()
{
return Width * Height;
}
}
public class Circle : Shape
{
public double Radius { get; set; }
public Circle(double radius)
{
Radius = radius;
}
public override double Square()
{
return Math.PI * Radius * Radius;
}
}Но правильней было бы написать так:
public static class Shapes
{
public abstract class Shape
{
public abstract TResult Match<TResult>(Func<double, double, TResult> rectangle, Func<double, TResult> circle);
}
public class Rectangle : Shape
{
public double Width { get; }
public double Height { get; }
public Rectangle(double width, double height)
{
Width = width;
Height = height;
}
public override TResult Match<TResult>(Func<double, double, TResult> rectangle, Func<double, TResult> circle)
{
return rectangle(Width, Height);
}
}
public class Circle : Shape
{
public double Radius { get; }
public Circle(double radius)
{
Radius = radius;
}
public override TResult Match<TResult>(Func<double, double, TResult> rectangle, Func<double, TResult> circle)
{
return circle(Radius);
}
}
public static double Sqare(Shape shape)
{
return shape.Match((w, h) => w * h, r => Math.PI * r * r);
}
}Между этими двумя реализациями есть принципиальная разница. В первом ("ООП") варианте нам легко добавить Треугольник, но чтобы добавить Периметр, придётся переписывать все классы. В втором ("ФП") варианте нам легко добавить Периметр, но чтобы добавить Треугольник, придётся переписывать все функции. Я не знаю, как объяснить эту разницу, не приводя примеры C# кода.
Ну как же отсутствие циклов, если цикл сделали. Который под капотом устроен на концевой рекурсии. Которая ещё более под капотом (что там компилятор накомпилирует) устроена опять как цикл.
"Функциональный дух" в виде "ФП - это процедурное программирование для бедных"?
Любой процедурщик прямо трактует цикл while как контракт! "Вышли из цикла = условие стало ложным". А если он это не делает, то он видимо ещё не наелся макарон в коде.
Но функциональные макароны ничем не лучше процедурных. И здесь они тоже есть: мы вывернули доступ к подмассивам мясом наружу, играем в конечные головы бесконечных списков и всё такое. Хотя умом-то понимаем, что никакие это не списки, а тупо двумерный массив, который нам проще создавать на встроенном в синтаксис списке, нежели тащить специальную библиотеку.
Ну как же отсутствие циклов, если цикл сделали. Который под капотом устроен на концевой рекурсии. Которая ещё более под капотом (что там компилятор накомпилирует) устроена опять как цикл.
Здесь ключевая фраза - "под капотом". Понятно, что у любой программы под капотом условные и безусловные переходы, но это не имеет значения. Важно то, рассуждаю ли я в терминах условных и безусловных переходов во время написания программы.
Цикл - это абстракция (многократное повторение одной и той же последовательности команд), которая может использоваться при написании кода.
mov x0, #0 // помещаем в регистр X0 число 0
b compare // переходим к проверке условия
while:
add x0, x0, #1 // X0 = X0 + 1
compare:
cmp x0, #5 // сравнивание значение регистра X0 с числом 5
b.lt while Если кто-то видит здесь цикл, то этот цикл только у него в голове. Для того, чтобы написать подобный код, необязательно знать про абстракцию "цикл". А можно написать подобный код именно как реализацию цикла.
until p f = go
where
go x | p x = x
| otherwise = go (f x)То же самое можно сказать и про хвостовую рекурсию. Здесь нет цикла. Хотя, возможно, этот код написал "императивщик", который не привык программировать с помощью абстракции "рекурсия", но знает, что цикл можно реализовать с помощью хвостовой рекурсии.
Оптимизация хвостовой рекурсии не использует цикл. Упрощённо, она заключается в том, что вместо размещения в стеке нового блока данных, необходимых для вызова функции, модифицируется уже имеющийся блок данных. То, что хвостовую рекурсии можно заменить циклом, не делает её циклом.
"Функциональный дух" в виде "ФП - это процедурное программирование для бедных"?
Нет. Это (в том числе) использование абстракций более высокого порядка вместо абстракции "цикл". То есть, когда во время написания кода программист рассуждает не "тут нам нужен цикл по элементам списка, который мы реализуем с помощью рекурсии", а "тут нам нужна свёртка списка по функции f". А если копнуть глубже, то "функциональный дух" - это рассуждения в духе "что нам нужно получить", а не "какие действия нужно сделать, чтобы это получить".
"Мы вставили абстракцию цикл Ц-слово, но мы не хотим, чтобы про неё думали, как про Ц-слово, поэтому давайте напишем на концевой рекурсии, расскажем сказку про контракт (процедурщики и так знают, что такое постусловие Ц-слова), а чтобы уж наверняка, назовём нашу функцию высшего порядка Ц-словом! чтоб никто не догадался"
Цикл он и есть цикл.
Хотелось бы функциональщины, - ввели бы
1) генератор многократных применений функции: проекция типа T на T* (бесконечный список)
2) фильтр по предикату
iterate f x = x : iterate f (f x)
filter p xs = [x | x <- xs, p x]
until p f x = head (filter p (iterate f x))и вуаля, мы тут мыслим в терминах данных (бесконечный ленивый список и его элементы), а не в терминах процессов (вызывать f раз за разом)
А насчёт того, что "этот код писал императивщик", так как раз императивщик и задумается о плане вычислений, и о том, что концевая рекурсия лучше обычной, как раз потому, что не жрёт память (и потому что реализуется через Ц-слово).
А вот декларативщик, который говорит "нам пофиг, как оно вычислится, мы выдвинули требования к результату" может отхватить люлей. Причём в хаскелле с его ленивостью он эти люли отхватит, если перепутает направления свёртки. Вы ведь знаете, почему правый фолд предпочтителен ленивый, а левый - предпочтителен энергичный (хотя и ленивый тоже есть для комплектности) Казалось бы какая разница, ленивый-энергичный, итог-то один, а? А императивщик сразу руками замашет.
Цикл он и есть цикл.
Рекурсия. Код я привёл.
и потому что реализуется через Ц-слово
Не знаю, зачем Вы написали свой вариант кода, но в нём нет хвостовой рекурсии.
Вы ведь знаете, почему правый фолд предпочтителен ленивый, а левый - предпочтителен энергичный
Знаю. В статье об этом написано.
Я привёл чисто декларативный код: "первый (или любой) элемент из последовательности многократных применений f к x, такой, что удовлетворяет заданному условию".
Причём эта формулировка позволяет делать всякие улучшения.
Например, обнаруживать зацикливание. Хоть самое простое, когда функция попала в неподвижную точку, fx = x. Хоть когда попала в цикл произвольной длины, f^n(x) = x.
Или обнаруживать ошибки в коде. Мы утверждаем, что функция монотонная (на каждом шаге мы уточняем игровое поле). То есть, x <= fx. И из этого следует, что возможны только циклы длиной 1 - неподвижные точки. Но если это не так, то пара смежных элементов x1, x2 с нарушением порядка, x1>x2, говорит, что ой всё.
Потому что мы исследуем последовательности как структуры данных.
А код "вызывать функцию и проверять условие, вызывать и проверять..." - это та самая императивность. Записанная посредством функционального языка. На языке с переменными и циклами это просто контракт - постусловие. "Если программа останавливается, то из этого следует, что постусловие выполнено". Очень даже декларативно, не? Если не накрутить макарон внутри цикла. Ну так макароны и в функциональном коде можно накрутить.
Я привёл чисто декларативный код
Теперь понял, зачем. Только снаружи осталось то же самое: "until p f x". Реализация не имеет значения. Например, можно сортировку списка реализовать так: перегоняем список в массив, сортируем на месте, перегоняем в список. И такая реализация не сделает код, использующий сортировку, менее функциональным.
По моему, у нас получается спор о терминах, что заведомо нерационально.
Вот именно. Вы знаете про ленивый и энергичный фолды. Собственно, любой хаскельщик это вынужден знать. Но это как раз императивная сторона языка, понимание того, в каком порядке что вычисляется, и указание вычислять именно в таком порядке.
Но если уж писать об этом, - то надо не вскользь, а раскрыть тему. Почему в энергичных языках правый фолд плохой, и его надо переписать на левый над перевёрнутым списком, например.
+1 поставил ошибочно. промахнулся мимо "ответить".
"Для простоты наложим на входные данные два дополнительных условия: решение всегда есть и его можно найти без перебора."
Некоторые однозначные решения можно и без перебора находить, но со взглядом на всю доску, а не на одну конкретную клетку с соседями.
Например, если у нас расставлены восемь единичек, то очевидно, где должна оказаться последняя девятая.
Вообще, модель данных "знаем конкретную цифру / не знаем ничего" - неоптимальна. Нужно "здесь заведомо могут быть такие-то цифры" - и когда это множество схлопнется до единственной цифры, тогда мы вообще молодцы. То есть, как бы, решаем не в двумерном десятеричном массиве, а в трёхмерном двоичном.
О функциональном программировании на примере решения судоку