Какую задачу лучше всего выполнить в стиле функционального программирования?
Я только недавно открыл стиль функционального программирования, и я убежден, что он сократит усилия по разработке, облегчит чтение кода, сделает программное обеспечение более понятным. Тем не менее, проблема в том, что я не могу никого убедить.
Ну, недавно мне дали возможность выступить с докладом о том, как сократить усилия по разработке и сопровождению программного обеспечения, и я хотел представить им концепцию функционального программирования и то, как это приносит пользу команде. У меня была идея показать людям 2 набора кода, которые делают одно и то же, один код написан очень настоятельно, а другой очень функционально, чтобы показать, что функциональное программирование может сделать код намного короче, проще для понимания и Таким образом, ремонтопригодны. Есть ли такой пример, кроме знаменитого примера суммы квадратов Луки Болоньезе?
16 ответов
Я только недавно открыл для себя стиль функционального программирования [...] Что ж, недавно мне дали возможность выступить с докладом о том, как сократить усилия по разработке программного обеспечения, и я хотел представить концепцию функционального программирования.
Если вы только что открыли для себя функциональное программирование, я не рекомендую пытаться авторитетно говорить на эту тему. Я знаю, что в течение первых 6 месяцев, пока я изучал F#, весь мой код был просто C# с немного более неловким синтаксисом. Однако по прошествии этого времени я смог написать стабильно хороший код в идиоматическом, функциональном стиле.
Я рекомендую вам сделать то же самое: подождите 6 месяцев или около того, пока стиль функционального программирования не станет более естественным, а затем сделайте презентацию.
Я пытаюсь проиллюстрировать преимущества функционального программирования, и у меня была идея показать людям 2 набора кода, который выполняет одно и то же: один код написан очень настоятельно, а другой - очень функционально, чтобы показать, что Функциональное программирование может сделать код намного короче, проще для понимания и, следовательно, поддержки. Есть ли такой пример, кроме знаменитого примера суммы квадратов Луки Болоньезе?
Я провел презентацию F# для группы пользователей.NET в моем регионе, и многие люди в моей группе были впечатлены сопоставлением с образцом F#. В частности, я показал, как обходить абстрактное синтаксическое дерево в C# и F#:
using System;
namespace ConsoleApplication1
{
public interface IExprVisitor<t>
{
t Visit(TrueExpr expr);
t Visit(And expr);
t Visit(Nand expr);
t Visit(Or expr);
t Visit(Xor expr);
t Visit(Not expr);
}
public abstract class Expr
{
public abstract t Accept<t>(IExprVisitor<t> visitor);
}
public abstract class UnaryOp : Expr
{
public Expr First { get; private set; }
public UnaryOp(Expr first)
{
this.First = first;
}
}
public abstract class BinExpr : Expr
{
public Expr First { get; private set; }
public Expr Second { get; private set; }
public BinExpr(Expr first, Expr second)
{
this.First = first;
this.Second = second;
}
}
public class TrueExpr : Expr
{
public override t Accept<t>(IExprVisitor<t> visitor)
{
return visitor.Visit(this);
}
}
public class And : BinExpr
{
public And(Expr first, Expr second) : base(first, second) { }
public override t Accept<t>(IExprVisitor<t> visitor)
{
return visitor.Visit(this);
}
}
public class Nand : BinExpr
{
public Nand(Expr first, Expr second) : base(first, second) { }
public override t Accept<t>(IExprVisitor<t> visitor)
{
return visitor.Visit(this);
}
}
public class Or : BinExpr
{
public Or(Expr first, Expr second) : base(first, second) { }
public override t Accept<t>(IExprVisitor<t> visitor)
{
return visitor.Visit(this);
}
}
public class Xor : BinExpr
{
public Xor(Expr first, Expr second) : base(first, second) { }
public override t Accept<t>(IExprVisitor<t> visitor)
{
return visitor.Visit(this);
}
}
public class Not : UnaryOp
{
public Not(Expr first) : base(first) { }
public override t Accept<t>(IExprVisitor<t> visitor)
{
return visitor.Visit(this);
}
}
public class EvalVisitor : IExprVisitor<bool>
{
public bool Visit(TrueExpr expr)
{
return true;
}
public bool Visit(And expr)
{
return Eval(expr.First) && Eval(expr.Second);
}
public bool Visit(Nand expr)
{
return !(Eval(expr.First) && Eval(expr.Second));
}
public bool Visit(Or expr)
{
return Eval(expr.First) || Eval(expr.Second);
}
public bool Visit(Xor expr)
{
return Eval(expr.First) ^ Eval(expr.Second);
}
public bool Visit(Not expr)
{
return !Eval(expr.First);
}
public bool Eval(Expr expr)
{
return expr.Accept(this);
}
}
public class PrettyPrintVisitor : IExprVisitor<string>
{
public string Visit(TrueExpr expr)
{
return "True";
}
public string Visit(And expr)
{
return string.Format("({0}) AND ({1})", expr.First.Accept(this), expr.Second.Accept(this));
}
public string Visit(Nand expr)
{
return string.Format("({0}) NAND ({1})", expr.First.Accept(this), expr.Second.Accept(this));
}
public string Visit(Or expr)
{
return string.Format("({0}) OR ({1})", expr.First.Accept(this), expr.Second.Accept(this));
}
public string Visit(Xor expr)
{
return string.Format("({0}) XOR ({1})", expr.First.Accept(this), expr.Second.Accept(this));
}
public string Visit(Not expr)
{
return string.Format("Not ({0})", expr.First.Accept(this));
}
public string Pretty(Expr expr)
{
return expr.Accept(this).Replace("(True)", "True");
}
}
class Program
{
static void TestLogicalEquivalence(Expr first, Expr second)
{
var prettyPrinter = new PrettyPrintVisitor();
var eval = new EvalVisitor();
var evalFirst = eval.Eval(first);
var evalSecond = eval.Eval(second);
Console.WriteLine("Testing expressions:");
Console.WriteLine(" First = {0}", prettyPrinter.Pretty(first));
Console.WriteLine(" Eval(First): {0}", evalFirst);
Console.WriteLine(" Second = {0}", prettyPrinter.Pretty(second));
Console.WriteLine(" Eval(Second): {0}", evalSecond);;
Console.WriteLine(" Equivalent? {0}", evalFirst == evalSecond);
Console.WriteLine();
}
static void Main(string[] args)
{
var P = new TrueExpr();
var Q = new Not(new TrueExpr());
TestLogicalEquivalence(P, Q);
TestLogicalEquivalence(
new Not(P),
new Nand(P, P));
TestLogicalEquivalence(
new And(P, Q),
new Nand(new Nand(P, Q), new Nand(P, Q)));
TestLogicalEquivalence(
new Or(P, Q),
new Nand(new Nand(P, P), new Nand(Q, Q)));
TestLogicalEquivalence(
new Xor(P, Q),
new Nand(
new Nand(P, new Nand(P, Q)),
new Nand(Q, new Nand(P, Q)))
);
Console.ReadKey(true);
}
}
}
Код выше написан в идиоматическом стиле C#. Он использует шаблон посетителя, а не типовое тестирование, чтобы гарантировать безопасность типов. Это около 218 LOC.
Вот версия F#:
#light
open System
type expr =
| True
| And of expr * expr
| Nand of expr * expr
| Or of expr * expr
| Xor of expr * expr
| Not of expr
let (^^) p q = not(p && q) && (p || q) // makeshift xor operator
let rec eval = function
| True -> true
| And(e1, e2) -> eval(e1) && eval(e2)
| Nand(e1, e2) -> not(eval(e1) && eval(e2))
| Or(e1, e2) -> eval(e1) || eval(e2)
| Xor(e1, e2) -> eval(e1) ^^ eval(e2)
| Not(e1) -> not(eval(e1))
let rec prettyPrint e =
let rec loop = function
| True -> "True"
| And(e1, e2) -> sprintf "(%s) AND (%s)" (loop e1) (loop e2)
| Nand(e1, e2) -> sprintf "(%s) NAND (%s)" (loop e1) (loop e2)
| Or(e1, e2) -> sprintf "(%s) OR (%s)" (loop e1) (loop e2)
| Xor(e1, e2) -> sprintf "(%s) XOR (%s)" (loop e1) (loop e2)
| Not(e1) -> sprintf "NOT (%s)" (loop e1)
(loop e).Replace("(True)", "True")
let testLogicalEquivalence e1 e2 =
let eval1, eval2 = eval e1, eval e2
printfn "Testing expressions:"
printfn " First = %s" (prettyPrint e1)
printfn " eval(e1): %b" eval1
printfn " Second = %s" (prettyPrint e2)
printfn " eval(e2): %b" eval2
printfn " Equilalent? %b" (eval1 = eval2)
printfn ""
let p, q = True, Not True
let tests =
[
p, q;
Not(p), Nand(p, p);
And(p, q),
Nand(Nand(p, q), Nand(p, q));
Or(p, q),
Nand(Nand(p, p), Nand(q, q));
Xor(p, q),
Nand(
Nand(p, Nand(p, q)),
Nand(q, Nand(p, q))
)
]
tests |> Seq.iter (fun (e1, e2) -> testLogicalEquivalence e1 e2)
Console.WriteLine("(press any key)")
Console.ReadKey(true) |> ignore
Это 65 LOC. Поскольку он использует сопоставление с шаблоном, а не с шаблоном посетителя, мы не теряем никакой безопасности типов, и код очень легко читается.
Любая символьная обработка на порядки проще написать на F#, чем на C#.
[Изменить, чтобы добавить:] О, и сопоставление с образцом не просто замена для шаблона посетителя, оно также позволяет сопоставить форму данных. Например, вот функция, которая преобразует Nand в их эквиваленты:
let rec simplify = function
| Nand(p, q) when p = q -> Not(simplify p)
| Nand(Nand(p1, q1), Nand(p2, q2))
when equivalent [p1; p2] && equivalent [q1; q2]
-> And(simplify p1, simplify q1)
| Nand(Nand(p1, p2), Nand(q1, q2))
when equivalent [p1; p2] && equivalent [q1; q2]
-> Or(simplify p1, simplify q1)
| Nand(Nand(p1, Nand(p2, q1)), Nand(q2, Nand(p3, q3)))
when equivalent [p1; p2; p3] && equivalent [q1; q2; q3]
-> Xor(simplify p1, simplify q1)
| Nand(p, q) -> Nand(simplify p, simplify q)
| True -> True
| And(p, q) -> And(simplify p, simplify q)
| Or(p, q) -> Or(simplify p, simplify q)
| Xor(p, q) -> Xor(simplify p, simplify q)
| Not(Not p) -> simplify p
| Not(p) -> Not(simplify p)
Это невозможно написать этот код кратко на C#.
Существует множество примеров, но ни один из них не будет настолько полным, как использование примера, относящегося к одному из ваших проектов на работе. Такие примеры, как "Сумма квадратов" Луки, потрясающие, но если бы кто-то использовал это как доказательство того, как наша кодовая база могла бы быть написана лучше, я бы не был убежден. Все это доказывает, что некоторые вещи лучше написаны функционально. Что вам нужно доказать, так это то, что ваша кодовая база лучше написана функционально
Я бы посоветовал выбрать некоторые популярные проблемные точки и некоторые ключевые точки в базе кода и переписать их в функциональном стиле. Если вы сможете продемонстрировать существенно лучшее решение, оно будет иметь большое значение для победы над коллегами.
Задачи для функционального стиля? В любое время у вас есть общий шаблон кодирования и вы хотите уменьшить его. Некоторое время назад я немного написал об использовании C# для функционального стиля, при этом убедившись, что он практичен: практический функционал C# (я не решаюсь ссылаться на свои собственные материалы, но думаю, что в данном случае это актуально). Если у вас есть обычное "корпоративное" приложение, показывать, скажем, как хороши выражения в сопоставлении с образцом, не будет слишком убедительно.
Но в реальных приложениях существует множество шаблонов, которые появляются на низком уровне кодирования. Используя функции более высокого порядка, вы можете заставить их уйти. Как я показываю в этом наборе постов в блоге, мой любимый пример - шаблон WCF "try-close/finally-abort". Шаблон try/finally-dispose настолько распространен, что превратился в ключевое слово языка: using. То же самое для "замка". Они оба тривиально представлены как функции более высокого порядка, и только потому, что C# изначально не поддерживал их, нам нужны жестко закодированные ключевые слова для их поддержки. (Быстро: выключите ваши блокировочные блоки, чтобы использовать блокировку ReaderWriter. Ой, сначала нам нужно написать функцию более высокого порядка.)
Но, возможно, чтобы убедить, нужно просто взглянуть на Microsoft. Генерика ака параметрический полиморфизм? Это вряд ли ОО, но хорошая функциональная концепция, которая теперь всем нравится. Милый фреймворк Ninject не будет работать без него. Лямбда? Как деревья выражений, они - то, как LINQ, Fluent NHibernate и т. Д. Получают всю свою силу. Опять же, это не из ОО или императивного программирования. Новая библиотека потоков? Довольно безобразно без замыканий.
Итак, функциональное программирование благословляет такие вещи, как.NET в течение последнего десятилетия. Основные достижения (такие как дженерики, "LINQ") происходят непосредственно из функциональных языков. Почему бы не осознать, что в этом что-то есть, и больше участвовать в этом? Вот как я бы сказал это скептикам.
Большая проблема - заставить людей совершить прыжок в понимании функций более высокого порядка. Хотя это довольно легко, если вы никогда не видели этого раньше в своей жизни, это может быть шокирующим и непостижимым. (Черт, многие считают, что дженерики предназначены только для безопасных типов коллекций, а LINQ - это просто встроенный SQL.)
Итак, что вы должны сделать, это пройти через свою кодовую базу и найти места, которые являются чрезмерно сложным императивным кошмаром. Ищите базовые шаблоны и используйте функции, чтобы аккуратно связать их вместе. Если вы не можете их найти, вы можете просто демо-списки. Например, "найти все Foos в этом списке и удалить их". Это функциональность в 1 строку в функциональном стиле "myList.Remove(x=>x.Bla > 0)" по сравнению с 7 строками в стиле C# (создание временного списка, циклическое переключение и добавление элементов для удаления, создание циклов и удаление элементов).).
Надежда состоит в том, что, хотя синтаксис странный, люди узнают: "Вау, это намного проще". Если они могут на некоторое время записать "многословно == более читабельно" и "выглядит странно", у вас будет шанс.
Удачи.
Лучшей пропагандистской статьей, когда-либо написанной для функционального стиля, является статья Джона Хьюза " Почему функциональное программирование имеет значение". Я предлагаю вам сделать несколько примеров для себя, пока вы не достигнете стадии, на которой вы сможете убедительно привести аргументы, изложенные в этой статье.
Многие из приведенных в статье примеров являются числовыми и не соответствуют современной аудитории. Еще одно современное упражнение, которое я дал своим ученикам, заключалось в том, чтобы использовать идеи, изложенные в этой статье, для упаковки больших медиафайлов на 4,7 ГБ DVD-диски для резервного копирования. Они использовали алгоритм "пузырькового поиска" Михаэля Митценмахера для создания альтернативных упаковок, и используя этот алгоритм и методы Хьюза, было легко получить каждый DVD (кроме последнего) заполненным на 99,9%. Очень мило.
По сути, функциональная парадигма очень эффективна для параллельной обработки:
"Что действительно интересно, я хочу, чтобы вы заметили здесь, это то, что как только вы думаете о карте и сокращаете ее как функции, которые могут использовать все, и они их используют, вам нужно всего лишь одного супергения, чтобы написать жесткий код для запуска отображать и сокращать глобальный массив параллельных компьютеров, и весь старый код, который работал нормально, когда вы только что запустили цикл, все еще работает только в миллиард раз быстрее, что означает, что его можно использовать для мгновенного решения огромных проблем.
Позвольте мне повторить это. Абстрагируясь от самой концепции зацикливания, вы можете реализовать зацикливание любым удобным для вас способом, в том числе реализовать его таким способом, который прекрасно масштабируется с помощью дополнительного оборудования ".
Чтобы достичь того, чего вы хотите, и сообщить об этом другим в вашей организации, вам нужно продемонстрировать, как бизнес вашей компании строится лучше.
Нет смысла использовать пару алгоритмов, чтобы продемонстрировать мощь функционального программирования, если оно абсолютно бесполезно для вашей бизнес-сферы. Итак, возьмите некоторый существующий код и переписайте его функционально. Если вы сможете доказать через это, что это лучше, люди будут вас слушать - вы показали им конкретный, соответствующий пример. Если вы не можете, то, возможно, функциональное программирование - это не решение, которое вы искали.
Если под "функциональным стилем" вы подразумеваете использование таких понятий, как "карта", "применить", "уменьшить", "фильтр", лямбда-функции и списки, то должно быть очевидно, что код, который имеет дело с операциями над списки почти всегда более кратки, когда написаны в "функциональном стиле". Но если вы смешиваете "функциональный стиль" с императивным кодом на преимущественно императивном языке, это действительно вопрос стиля.
Например, в python вы можете переопределить взломанный Haskell qsort, опубликованный так:
def qsort(list):
if list == []:
return []
else:
x = list[0]; xs = list[1:]
return qsort(filter(lambda y: y<x, xs)) + [x] + qsort(filter(lambda y: y>= x, xs))
Хотя писать последнюю строку как
return qsort([y for y in xs if y<x]) + [x] + qsort([y for y in xs if y>=x])
возможно более "питонический".
Но это, очевидно, более кратко, чем реализация здесь:
http://hetland.org/coding/python/quicksort.html
Кстати, именно так я и думал бы о его внедрении до того, как начал изучать Haskell.
Функциональная версия предельно ясна тогда и только тогда, когда вы привыкли к функциональному программированию и не знаете, что делать. filter собирается сделать так же легко, как утомленный программист C++ for цикл, даже не задумываясь об этом. И это ясно, что реальная проблема здесь поставлена: функциональное "стилевое" программирование - это совершенно другое мышление. Если люди, с которыми вы работаете, не привыкли мыслить рекурсивно и не из тех, кого волнуют, не просто из-за новой технологии, а из совершенно другого способа решения своих проблем, тогда любое количество сравнений кода не собираюсь побеждать их.
Другим примером может быть алгоритм быстрой сортировки. Это может быть очень кратко описано на функциональном языке, таком как Haskell:
qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
но нужно больше кодирования на итеративном языке. На указанном веб-сайте вы также можете найти множество других примеров сравнения языков.
Покажите им способ jQuery для перебора элементов DOM:
$(".magic-divs").click(function(){
// FYI, in this context, "this" will be the element clicked on.
alert("somebody clicked on " + this.id);
this.hide();
});
$(".magic-divs").show();
против того, как большинство результатов Google для "элемента JavaScript по имени класса" делают это:
var arrayOfElements = // this is filled with the elements somehow
for(var i=0,j=arrayOfElements.length; i<j; i++) {
alert("now I get to add an onclick event somehow " + i);
}
// i dont even want to type the ugly for-loop stuff to hide every div...
Функциональное программирование полезно в повседневных вещах, подобных описанным выше!
(примечание: я не знаю, соответствует ли мой пример точному определению функционального программирования, но если да, то функциональное программирование - это здорово)
Хорошим примером может служить создание собственного языка программирования с использованием существующего, где вам придется использовать монады.
С F# гораздо проще написать логику синтаксического анализа, чем с C#.
Взгляните на эту статью: Функциональные.NET - LINQ или языковые интегрированные монады?
Алгоритмы, включающие поиск в обратном направлении и упрощение поддержки отмены в графических интерфейсах, являются двумя местами, где я использовал функциональный стиль на практике.
Недавно я придумал небольшую хитрость, чтобы сделать лямбды, передаваемые в мои методы расширения, более похожими на F# иш. Здесь это идет:
То, что я хотел сделать, было что-то вроде:
3.Times(() => Console.WriteLine("Doin' it"));
Теперь метод расширения для этого легко реализуется:
public static void Times(this int times, Action action)
{
Enumerable.Range(1, times).ToList().ForEach(index => action());
}
Что мне не понравилось, так это то, что я указываю индекс здесь: ForEach(index => action()) хотя он никогда не используется, поэтому я заменил его _ и получил ForEach(_ => action())
Это хорошо, но теперь я был мотивирован, чтобы мой код вызова был похож
(Мне никогда не нравилось "()" в начале лямбда-выражения), поэтому вместо: 3.Times(() => ...); я хотел 3.Times(_ => ...);Единственный способ реализовать это - передать ложный параметр в метод расширения, который никогда не используется, и поэтому я изменил его так:
public static void Times(this int times, Action<byte> action)
{
Enumerable.Range(1, times).ToList().ForEach(_ => action(byte.MinValue));
}
Это позволяет мне называть это так:
3.Times(_ => Console.WriteLine("Doin' it"));
Ничего особенного, но я все еще наслаждался тем, что можно было так легко сделать эту небольшую подстройку и в то же время убрать шум "()", что делает его намного более читабельным.
Простым примером задачи, которую часто проще всего выполнить в функциональном стиле, является преобразование данных из одной формы в другую. "Сумма квадратов" является тривиальным примером преобразования данных. Выступление Луки на прошлогоднем PDC показало, как использовать такого рода преобразование данных для чего-то более практичного, загрузки и анализа котировок акций. Демонстрация сделана на F#, но концепции те же и могут быть применены к C# или большинству других языков программирования.
Не совсем отвечаю на вопрос, но это очень хорошая ссылка для тех, кто хочет знать о функциональном программировании на C#
http://blogs.msdn.com/b/ericwhite/archive/2006/10/04/fp-tutorial.aspx
Покажите, как кодировать отдельный массив. Отличить очень легко в SQL, но это было трудно для массива памяти. Теперь легко выделить массив с помощью LINQ.
Вы можете объяснить им, что в будущем будет parralel LINQ (PLINQ). Когда вы начнете писать функциональный код, вам будет проще провести параллелизацию вашего приложения. Google широко использует MapReduce.
Объясните им, что LINQ - это язык запросов для манипулирования всеми видами данных. В памяти, в базе данных, отлично, веб-сервисы, XML-файлы, JSON-файлы. Это какой-то универсальный SQL. Однако люди, которые не любят SQL, будут менее убеждены.
Я бы не стал много говорить о функциональном программировании, я бы объяснил, как LINQ может помочь разработчикам.
Интересно, что никто так и не ответил на вопрос: какую задачу лучше всего выполнить в "функциональном стиле"?
Программа / алгоритм состоит из 2 частей: логическое управление и структура данных. Я думаю, что задачи, которые лучше всего выполнять в функциональном стиле, это те списки или массивы, в которых они работают, как списки (например, qsort). Не случайно, что функциональные языки программирования очень хорошо поддерживают списки.
Когда структуры данных отклоняются от списков, я думаю, что использование функционального стиля программирования становится немного "неестественным".