Какая задача лучше всего сделана в стиле функционального программирования?
Ваш код почти у цели. Хотя похвально не хотеть хранить все это в памяти, вам придется хранить совокупные компоненты предыдущей строки:
15 ответов
Я только недавно открыл для себя стиль функционального программирования [...] Ну, недавно мне дали возможность рассказать о том, как сократить усилия по разработке программного обеспечения, и я хотел представить концепцию функционального программирования. программирования.
Если вы только что открыли функциональное программирование, я не рекомендую пытаться авторитетно говорить на эту тему. Я знаю, что в течение первых 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 #.
Простым примером задачи, которую часто проще всего выполнить в функциональном стиле, является преобразование данных из одной формы в другую. «Сумма квадратов» является тривиальным примером преобразования данных. Выступление Луки на прошлогоднем PDC показало, как использовать этот вид преобразования данных для чего-то более практичного, загрузки и анализа котировок акций. Демонстрация сделана на F #, но концепции те же и могут быть применены к C # или большинству других языков программирования.
Алгоритмы, включающие поиск в обратном направлении и упрощение поддержки отмены в графических интерфейсах, являются двумя местами, где я использовал функциональный стиль на практике.
Чтобы достичь того, чего вы хотите, и сообщить об этом другим в вашей организации, вам нужно продемонстрировать, как бизнес вашей компании строится лучше.
Бесполезно использовать пару алгоритмов для демонстрации возможностей функционального программирования, если оно абсолютно бесполезно для вашей бизнес-сферы. Итак, возьмите некоторый существующий код и переписайте его функционально. Если вы сможете доказать, что это лучше, люди будут вас слушать - вы показали им конкретный, соответствующий пример. Если вы не можете, то, возможно, функциональное программирование - это не решение, которое вы искали.
Другим примером может служить алгоритм быстрой сортировки . Он может быть очень кратко описан на функциональном языке, таком как Haskell:
qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
, но нуждается в некотором дополнительном кодировании на итеративном языке. На указанном веб-сайте вы также можете найти множество других примеров сравнения языков.
По сути, функциональная парадигма очень эффективна для параллельной обработки:
«Здесь действительно интересно то, что я хочу, чтобы вы заметили, это то, что как только вы думаете о карте и сокращаете ее как функции что каждый может использовать, и они используют их, вам нужно всего лишь один супергений, чтобы написать жесткий код для запуска map и сокращения на глобально массивном параллельном массиве компьютеров, и весь старый код, который работал нормально, когда вы только запускали цикл по-прежнему работает только в миллиард раз быстрее, что означает, что его можно использовать для мгновенного решения огромных проблем.
Позвольте мне повторить это. Абстрагируясь от самой концепции цикла, вы можете реализовать цикл любым способом. хочу, в том числе реализовать его таким способом, который прекрасно масштабируется с дополнительным оборудованием. "
Если под «функциональным стилем» вы подразумеваете использование таких понятий, как «карта», «применить», «уменьшить», «фильтровать», лямбда-функции и списки, то должно быть очевидно, что код, который должен иметь дело с Операции со списками почти всегда более лаконичны при написании в «функциональном стиле». Но если вы смешиваете «функциональный стиль» с императивным кодом на преимущественно императивном языке, это действительно вопрос стиля.
В python, например, вы можете переопределить сообщение Haskell qsort crackmigg, опубликованное так:
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, даже не задумываясь об этом. И это ясно, что реальная проблема здесь поставлена: функциональное «стилевое» программирование - это совершенно другое мышление . Если люди, с которыми вы работаете, не привыкли мыслить рекурсивно и не из тех, кого волнует, не просто из-за новой технологии, а из совершенно другого способа решения своих проблем, тогда любое количество сравнений кода не требуется. не собираюсь побеждать их.
Покажите им способ 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...
Функциональное программирование полезно в повседневном материале как вышеупомянутое!
(примечание: Я не знаю, соответствует ли мой пример точному определению функционального программирования, но если это делает, чем функциональное программирование является потрясающим),
Лучшая работа поддержки, когда-либо написанная для функционального стиля, является статьей John Hughes под названием Почему Вопросы Функционального программирования. Я предлагаю, чтобы Вы сделали некоторые примеры для себя, пока Вы не достигаете стадии, где можно убедительно привести аргументы, размеченные в той газете.
Многие примеры в газете являются числовыми и не находят отклик у сегодняшних зрителей. Еще одно современное осуществление, которое я дал моим студентам, должно было использовать идеи в той газете для упаковки больших медиа-файлов на DVD на 4.7 ГБ для резервного копирования. Они использовали "пузырьковый поисковый" алгоритм Michael Mitzenmacher для генерации альтернативных упаковок, и использующий этот алгоритм и методы Hughes, было легко получить каждый DVD (кроме последнего) полные 99,9%. Очень сладкий.
Задачи для функционального стиля? Любое время Вы имеете общий шаблон кодирования и хотите уменьшить его. Только что я записал немного при использовании C# для функционального стиля при проверке, что это практично: Практический Функциональный C# (я, смущаются связываться с моим собственным материалом здесь, но я думаю, что это релевантно в этом случае). Если у Вас будет общее приложение "предприятия", показывая, скажем, как выражения прекрасны в сопоставлении с образцом, не будет слишком убедительно.
Но в реальных приложениях, существуют ТОННЫ шаблонов, которые открываются на низком, кодирующем уровне. Используя функции высшего порядка, можно заставить их уйти. Поскольку я показываю в том наборе сообщений в блоге, моим любимым примером является "try-close/finally-abort" шаблон WCF. "try/finally-dispose" шаблон так распространен, в него превратились ключевое слово языка: использование. То же самое для "блокировки". Они и тривиально представлены, поскольку высший порядок функционирует, и только потому, что C# не поддерживал их, первоначально делают нам нужны трудно кодированные ключевые слова языка для поддержки их. (Быстрый: выключите свои блоки "блокировки" для использования блокировки ReaderWriter. Ой, мы должны будем записать функцию высшего порядка сначала.)
Но возможно убеждение просто требует рассмотрения Microsoft. Дженерики иначе параметрический полиморфизм? Это - едва OO, но хорошее функциональное понятие, что, теперь, все любят. Милая платформа Ninject не работала бы без него. Лямбды? Как деревья выражений, они - то, как LINQ, Быстрый NHibernate, и т.д. получают все свое питание. Снова, это не прибывает из OO или императивного программирования. Новая библиотека Threading? Довольно ужасный без закрытий.
Так, функциональное программирование было вещами благословения как.NET за прошлое десятилетие. Важные шаги вперед (такие как дженерики, "LINQ") непосредственно с функциональных языков. Почему бы не понять существует что-то к нему, и свяжитесь больше с ним? Это - то, как я формулировал бы его скептикам.
Большая проблема на самом деле заставляет людей делать переход в понимании к функциям высшего порядка. В то время как довольно легко, если Вы никогда не видели его прежде в Вашей жизни, это могло бы потрясать непостижимое. (Heck, кажется, что много людей думает, что дженерики только для безопасных с точки зрения типов наборов, и LINQ является просто встроенный SQL.)
Так, что необходимо сделать, проходят кодовую базу и находят места, которые являются чрезмерно сложным обязательным кошмаром. Ищите базовые шаблоны и используйте функции для строкового представления его вместе приятно. Если Вы не можете найти никого, Вы могли бы согласиться просто demo'ing от списков. Например, "находят всего Foos в этом списке и удаляют их". Это - 1 вещь строки в функциональном стиле "myList. Удалите (x => x. Bla> 0)" по сравнению с 7 строками в стиле C# (создают временный список, цикл через и добавляют к - удаляют объекты, цикл, хотя и удаляют объекты).
Надежда состоит в том, что, даже при том, что синтаксис нечетен, люди распознают, "ничего себе, это намного более просто". Если они могут подавить "подробный == более читаемый" и, "который выглядит сбивающим с толку" некоторое время, у Вас будет шанс.
Удачи.
Существует много примеров там, но ни один не будет как влияние, полное как использование образца, относящегося к одному из Ваших проектов на работе. Примеры как "Сумма квадратов" Luca являются потрясающими, но если бы кто-то использовал это в качестве доказательства относительно того, как наша кодовая база могла быть записана лучше, я не был бы убежден. Весь пример доказывает, некоторые вещи, лучше, записал функционально. То, что необходимо доказать, является кодовой базой, лучше записан функционально
Мой совет состоял бы в том, чтобы выбрать некоторые популярные горячие точки и некоторые базовые места в кодовой базе, и переписать их в функциональном стиле. Если можно продемонстрировать существенно лучшее решение, оно будет иметь большое значение для победы над коллегами.
Хороший пример cood создать Ваш собственный язык программирования с помощью существующего, где необходимо будет использовать Монады.
С F# это - много много simplier для записи логики синтаксического анализа, чем с C#.
Смотрите на эту статью: Функциональная.NET - LINQ или Язык Интегрированные Монады?
-
Показать, как кодировать отдельный массив. Отличить очень легко в SQL, но это было трудно для массива памяти. Теперь легко определить массив с помощью LINQ.
-
Вы можете объяснить им, что в будущем будет parralel LINQ (PLINQ). Когда вы начнете писать функциональный код, вам будет проще провести параллелизацию вашего приложения. Google широко использует MapReduce.
-
Объясните им, что LINQ - это язык запросов для манипулирования всеми видами данных. В памяти, в базе данных, отлично, веб-сервисы, XML-файлы, JSON-файлы. Это какой-то универсальный SQL. Однако люди, которые не любят SQL, будут менее убеждены.
Я бы не стал много говорить о функциональном программировании, я бы объяснил, как 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"));
Не очень изменений, но я все еще наслаждался тем, что можно было так легко сделать эту небольшую подстройку, и в то же время устранение шума "()" делает его намного более читабельным.
Интересно, что никто действительно не ответил на вопрос: какая задача лучше всего сделана в "функциональном стиле"?
Программа/алгоритм состоит из 2 частей: логическая управляющая структура и структура данных. Я думаю, что задачами, лучше всего сделанными в функциональном стиле, являются те включенные списки или массивы в случаях, где они ведут себя как список (например, qsort). Это не совпадение, что языки функционального программирования имеют очень хорошую поддержку списков.
Когда структуры данных отклоняются от списков, я думаю, что использование стиля функционального программирования становится немного "неестественным".