Объяснение функционального программирования объектно-ориентированным программистам и менее техническим специалистам - PullRequest
22 голосов
/ 19 февраля 2010

Какие хорошие примеры я могу использовать для объяснения функционального программирования?

Аудитория - люди с небольшим опытом программирования или люди, имеющие только объектно-ориентированный опыт.

Ответы [ 12 ]

31 голосов
/ 19 февраля 2010

Аудитория была бы людьми с небольшой опыт программирования,

Действительно ли возможно объяснить функциональное программирование, пусть наряду с ОО или процедурным или любой парадигмой программирования людям без большого опыта программирования?

или людей, которые имеют только объектно-ориентированный опыт.

Ну, наверное, лучшими примерами будет преобразование известных шаблонов проектирования в их функциональный эквивалент. Давайте рассмотрим канонический пример преобразования списка целых в список строк:

using System;

namespace Juliet
{
    interface IConvertor<T, U>
    {
        U Convert(T value);
    }

    class Program
    {
        static U[] Convert<T, U>(T[] input, IConvertor<T, U> convertor)
        {
            U[] res = new U[input.Length];
            for (int i = 0; i < input.Length; i++)
            {
                res[i] = convertor.Convert(input[i]);
            }
            return res;
        }

        class SquareInt : IConvertor<int, string>
        {
            public string Convert(int i)
            {
                return (i * i).ToString();
            }
        }

        class ScaleInt : IConvertor<int, string>
        {
            readonly int Scale;

            public ScaleInt(int scale)
            {
                this.Scale = scale;
            }

            public string Convert(int i)
            {
                return (i * Scale).ToString();
            }
        }

        static void Main(string[] args)
        {
            int[] nums = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

            string[] squared = Convert<int, string>(nums, new SquareInt());
            string[] tripled = Convert<int, string>(nums, new ScaleInt(3));
        }
    }
}

Он простой, читаемый, объектно-ориентированный, даже универсальный, так что он работает для любых произвольных типов, так в чем же проблема? Для начала, это раздутый: у меня есть определение интерфейса и две реализации интерфейса. Что если мне понадобится еще одно обращение? Ну, мне нужна другая реализация интерфейса - она ​​может быстро выйти из-под контроля.

Когда вы думаете об этом, класс IConvertor<T, U> - это просто оболочка вокруг единственной функции с именем Convert - класс буквально существует, чтобы помочь нам передать Convert другим функциям. Если вы можете это понять, то вы уже понимаете основные принципы, лежащие в основе функций, как первоклассные значения - функциональное программирование - это передача функций другим функциям почти так же, как вы передаете человека, int или строку.

Люди обычно предпочитают функциональное программирование, потому что оно помогает им избегать однотипных интерфейсов и реализаций. Вместо того, чтобы передавать класс, мы просто передаем функцию по имени или анонимно:

using System;

namespace Juliet
{
    class Program
    {
        static U[] Convert<T, U>(T[] input, Func<T, U> convertor)
        {
            U[] res = new U[input.Length];
            for (int i = 0; i < input.Length; i++)
            {
                res[i] = convertor(input[i]);
            }
            return res;
        }

        static string SquareInt(int i)
        {
            return (i * i).ToString();
        }

        static void Main(string[] args)
        {
            int[] nums = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

            string[] squared = Convert<int, string>(nums, SquareInt); // pass function by name
            string[] tripled = Convert<int, string>(nums, i => (i * 3).ToString()); // or pass anonymously
        }
    }
}

Хорошо, теперь у нас точно такая же программа с гораздо меньшим количеством строк кода, она удобочитаема и очень наглядно показывает, что она делает.

Теперь кто-то может сказать: «Это изящный трюк, но когда бы я его использовал» - есть много случаев, когда вы хотели бы передавать функции таким образом. Это дает вам гораздо больше возможностей абстрагировать поток управления вашими программами новыми способами. Адаптировано из примера, показанного здесь , рассмотрим класс, который обрабатывает файлы:

class FileFunctions
{
    internal void SaveFile()
    {
        SaveFileDialog fileDialog = new SaveFileDialog();
        fileDialog.Filter = "Text files (*.txt)|*.txt|All files (*.*)|*.*";
        if (fileDialog.ShowDialog() == DialogResult.OK)
        {
            File.AppendAllText(fileDialog.FileName, MyDocument.Data);
        }
    }

    internal void WriteFile()
    {
        OpenFileDialog fileDialog = new OpenFileDialog();
        fileDialog.Filter = "Text files (*.txt)|*.txt|All files (*.*)|*.*";
        if (fileDialog.ShowDialog() == DialogResult.OK)
        {
            MyDocument.Data = File.ReadAllText(fileDialog.FileName);
        }
    }
}

Тьфу. Код повторяется, но он выполняет операции над разными классами и вызывает разные методы. Как бы вы абстрагировали дублированный код во вселенной OO? В функциональном программировании это тривиально:

class FileFunctions
{
    internal void ShowDialogThen(FileDialog dialog, Action<FileDialog> f)
    {
        dialog.Filter = "Text files (*.txt)|*.txt|All files (*.*)|*.*";
        if (dialog.ShowDialog() == DialogResult.OK)
        {
            f(dialog);
        }
    }

    internal void SaveFile()
    {
        ShowDialogThen(
            new SaveFileDialog(),
            dialog => File.AppendAllText(dialog.FileName, MyDocument.Data));
    }

    internal void WriteFile()
    {
        ShowDialogThen(
            new OpenFileDialog(),
            dialog => { MyDocument.Data = File.ReadAllText(dialog.FileName); });
    }
}

Высокий.

9 голосов
/ 19 февраля 2010

Сначала было бы проще описать функциональное программирование по его основным характеристикам:

  1. Функции (очевидно)
  2. Нет побочных эффектов
  3. Неизменность
  4. Рекурсия очень важна
  5. Очень распараллеливаемый

Из них наиболее важной характеристикой является понятие отсутствия побочных эффектов, поскольку другие характеристики вытекают из этого.

Функциональное программирование используется в местах, которые вы можете не ожидать. Он используется для запуска светофоров и коммутаторов связи (например, коммутаторы Ericsson работают на Erlang).

5 голосов
/ 19 февраля 2010

Те, у кого мало опыта в программировании, вероятно, проще, поскольку у них не будет столько концепций программирования, которые можно было бы найти: функциональное программирование очень похоже на математические функции в качестве выражений, поэтому покажите им немного математики.

Для ООП вы можете показать, как замыкания похожи на инкапсуляцию, и, следовательно, как функциональное программирование охватывает ООП. Вы также можете показать, насколько полезны функции высшего порядка, в частности, как они вызывают некоторые шаблоны ООП (такие как шаблоны «Стратегия» и «Шаблоны» и шаблон «Посетитель» в языках с мультиметодами), исчезают в языке ( утверждает Питер Норвиг) , что 16 из 23 шаблонов GOF проще в Dylan и Lisp ). Напротив, ООП на основе передачи сообщений (а не подход CLOS) представляет собой шаблон в FP, который невидим в ООП.

Продемонстрируйте, как легко писать общие арифметические выражения, наряду с составлением и дифференцированием функций, в качестве конструктов программирования, и вы получите оба из них.

Вы можете или не хотите показывать мультиметоды ОО людей CLOS; они будут или бунтовать или иметь гикгазм. В любом случае, это может быть грязно.

Некоторые другие возможности показать гибкость FP: ленивая оценка может быть реализована с помощью нулевых анонимных функций. FP может поддерживать как ООП на основе классов, так и на основе прототипов. Есть много других примеров (например, стиль прохождения продолжения), но они обычно требуют знакомства с FP перед обучением.

SICP имеет множество интересных примеров и проблем; это должно оказаться вдохновляющим.

3 голосов
/ 29 августа 2012

Функциональное программирование для объектно-ориентированного программиста by Brian Marick. Я не связан, или что-то, просто пришло это прямо сейчас:

https://leanpub.com/fp-oo

Дядя Боб любит это! :)

3 голосов
/ 20 февраля 2010

Почему вопросы функционального программирования Джона Хьюза содержат несколько хороших примеров, но даже лучше, они объясняют почему функциональных языков программирования, а не только как, Вы можете сделать намного хуже, чем создать презентацию на основе этой статьи!

3 голосов
/ 19 февраля 2010

OO составляет около существительных , в то время как функциональное программирование составляет около глаголов . Прочитайте этот довольно хороший блог на эту тему от Steve Yegge .

3 голосов
/ 19 февраля 2010

Попробуйте посмотреть эту статью под названием Функциональное программирование для остальных U с, ниже приведен отрывок.

В этой статье я объясню наиболее широко используемые идеи из функциональных языков на примерах, написанных на Java (да, вы можете писать функциональные программы на Java, если вы чувствуете себя особенно мазохистски). В следующих нескольких разделах мы рассмотрим Java как есть и внесем в нее изменения, чтобы преобразовать ее в полезный функциональный язык. Давайте начнем наш квест.

2 голосов
/ 20 февраля 2010

Неизменяемые структуры данных

Знаете, я уже комментировал людям о функциональном программировании и поднял вопрос о "неизменяемой структуре данных".Обычно это поражает воображение людей. Как вы должны добавить что-то в коллекцию, если не можете добавить ее?

Непосредственный ответ: «Ну, вы не делаете, вы просто создаете новую версиюваша структура данных с добавленным объектом ", и немедленный ответ" это звучит не очень эффективно ".Ну, это так.

Неизменяемый стек

Каноническая неизменяемая структура данных - это неизменяемый стек, который в основном представляет собой узел, содержащий два значения только для чтения: голова и хвост.Толкание и выталкивание из стопки - O (1).Индексные поиски, вставки / удаления в середине списка требуют времени O (n), что, к слову, совпадает с изменяемым стеком.

using System;

namespace Juliet
{
    public abstract class Stack<T>
    {
        public static readonly Stack<T> Empty = new Nil();

        public abstract T Head { get; }
        public abstract Stack<T> Tail { get; }
        public abstract bool IsEmpty { get; }
        public Stack<T> Push(T value) { return new Cons(value, this); }
        public Stack<T> Append(Stack<T> other)
        {
            if (this.IsEmpty) { return other; }
            else { return new Cons(this.Head, this.Tail.Append(other)); }
        }

        sealed class Nil : Stack<T>
        {
            public override T Head { get { throw new Exception("Empty stack"); } }
            public override Stack<T> Tail { get { throw new Exception("Empty stack"); } }
            public override bool IsEmpty { get { return true; } }
        }

        sealed class Cons : Stack<T>
        {
            private readonly T _head;
            private readonly Stack<T> _tail;

            public override T Head { get { return _head; ; } }
            public override Stack<T> Tail { get { return _tail; } }
            public override bool IsEmpty { get { return false; } }

            public Cons(T head, Stack<T> tail)
            {
                _head = head;
                _tail = tail;
            }
        }
    }

    class Program
    {       
        static void Main(string[] args)
        {
            var s = Stack<int>.Empty.Push(1).Push(2).Push(3).Push(4).Push(5);
            while (!s.IsEmpty)
            {
                Console.Write("{0} ", s.Head);
                s = s.Tail;
            }
            Console.ReadKey(true);
        }
    }
}

Неизменяемое дерево AVL

Большинство людей не впечатлены стеками, потому что это не «серьезная» структура данных, но деревья AVL и другие самобалансирующиеся структуры данных впечатляют.Деревья на самом деле очень легко записать в виде неизменных структур данных.

Эта версия поддерживает O (log n) вставки и поиск, удаление не показано, но также может быть реализовано в O (log n).Другими словами, неизменяемое дерево AVL имеет ту же вычислительную сложность, что и его изменяемый вариант:

using System;
using System.Linq;

namespace Juliet
{
    public abstract class AvlTree<T>
        where T : IComparable<T>
    {
        static AvlTree<T> Make(AvlTree<T> left, T value, AvlTree<T> right)
        {
            return new Node(left, value, right, Math.Max(left.Height, right.Height) + 1, left.Count + right.Count + 1);
        }

        public static readonly AvlTree<T> Empty = new Nil();

        protected abstract AvlTree<T> Left { get; }
        protected abstract AvlTree<T> Right { get; }
        protected abstract T Value { get; }
        public abstract int Height { get; }
        public abstract int Count { get; }

        public bool Contains(T v)
        {
            if (this.Height == 0) { return false; }
            else
            {
                int compare = v.CompareTo(this.Value);
                if (compare < 0) { return this.Left.Contains(v); }
                else if (compare > 0) { return this.Right.Contains(v); }
                else { return true; }
            }
        }

        public AvlTree<T> Insert(T v)
        {
            if (this.Height == 0) { return Make(this, v, this); }
            else
            {
                int compare = v.CompareTo(this.Value);
                if (compare < 0) { return Balance(Make(this.Left.Insert(v), this.Value, this.Right)); }
                else if (compare > 0) { return Balance(Make(this.Left, this.Value, this.Right.Insert(v))); }
                else { return this; }
            }
        }

        private static AvlTree<T> Balance(AvlTree<T> tree)
        {
            if (tree.Height > 0)
            {
                int outerBalanceFactor = tree.Left.Height - tree.Right.Height;
                if (outerBalanceFactor <= -2 && tree.Right.Height > 0) // right-side too heavy
                {
                    int innerBalanceFactor = tree.Right.Left.Height - tree.Right.Right.Height;
                    if (innerBalanceFactor <= -1) // right-right case
                    {
                        return LeftRotate(tree);
                    }
                    else if (innerBalanceFactor >= 1) // right-left case
                    {
                        return DoubleLeftRotate(tree);
                    }
                }
                else if (outerBalanceFactor >= 2 && tree.Left.Height > 0) // left-side too heavy
                {
                    int innerBalanceFactor = tree.Left.Left.Height - tree.Left.Right.Height;
                    if (innerBalanceFactor <= -1) // left-left case
                    {
                        return DoubleRightRotate(tree);
                    }
                    else if (innerBalanceFactor >= 1) // left-right case
                    {
                        return RightRotate(tree);
                    }
                }
            }
            return tree;
        }

        private static AvlTree<T> LeftRotate(AvlTree<T> tree)
        {
            if (tree.Height > 0 && tree.Right.Height > 0)
            {
                T p = tree.Value;
                T q = tree.Right.Value;
                AvlTree<T> a = tree.Left;
                AvlTree<T> b = tree.Right.Left;
                AvlTree<T> c = tree.Right.Right;
                return Make(Make(a, p, b), q, c);
            }
            return tree;
        }

        private static AvlTree<T> RightRotate(AvlTree<T> tree)
        {
            if (tree.Height > 0 && tree.Left.Height > 0)
            {
                T q = tree.Value;
                T p = tree.Left.Value;
                AvlTree<T> a = tree.Left.Left;
                AvlTree<T> b = tree.Left.Right;
                AvlTree<T> c = tree.Right;
                return Make(a, p, Make(b, q, c));
            }
            return tree;
        }

        private static AvlTree<T> DoubleLeftRotate(AvlTree<T> tree)
        {
            if (tree.Height > 0)
            {
                // right-rotate right child, left-rotate root
                return LeftRotate(Make(tree.Left, tree.Value, RightRotate(tree.Right)));
            }
            return tree;
        }

        private static AvlTree<T> DoubleRightRotate(AvlTree<T> tree)
        {
            if (tree.Height > 0)
            {
                // left-rotate left child, right-rotate root
                return RightRotate(Make(LeftRotate(tree.Left), tree.Value, tree.Right));
            }
            return tree;
        }


        sealed class Nil : AvlTree<T>
        {
            protected override AvlTree<T> Left { get { throw new Exception("Empty tree"); } }
            protected override AvlTree<T> Right { get { throw new Exception("Empty tree"); } }
            protected override T Value { get { throw new Exception("Empty tree"); } }
            public override int Height { get { return 0; } }
            public override int Count { get { return 0; } }
        }

        sealed class Node : AvlTree<T>
        {
            readonly AvlTree<T> _left;
            readonly AvlTree<T> _right;
            readonly T _value;
            readonly int _height;
            readonly int _count;

            protected override AvlTree<T> Left { get { return _left; } }
            protected override AvlTree<T> Right { get { return _right; } }
            protected override T Value { get { return _value; } }
            public override int Height { get { return _height; } }
            public override int Count { get { return _count; } }

            public Node(AvlTree<T> left, T value, AvlTree<T> right, int height, int count)
            {
                _left = left;
                _right = right;
                _value = value;
                _height = height;
                _count = count;
            }
        }
    }

    class Program
    {       
        static void Main(string[] args)
        {
            var tree = AvlTree<int>.Empty;
            foreach(int i in Enumerable.Range(1, 1000000).OrderBy(_ => Guid.NewGuid()))
            {
                tree = tree.Insert(i);
            }

            Console.Write("Tree height: {0}, tree count: {1}", tree.Height, tree.Count);

            Console.ReadKey(true);
        }
    }
}
1 голос
/ 19 февраля 2010

Мы использовали этот урок для Haskell, и он работал очень хорошо, его легкомысленно, но хорошо справляется с объяснениями:

Учим вас на Haskell для хорошего блага

1 голос
/ 19 февраля 2010

Я не думаю, что вы можете, честно говоря.Функциональное программирование (например, «хорошее» ОО-программирование или «процедурное с классами») требует изменения умственной модели.Вы просто не можете понять это как процедурный кодер, не потратив время и не потратив время на его использование.

Если вы действительно хотите, чтобы кто-то разбирался в функциональном программировании, достаньте ему копию Little Schemer или какой-то другой эквиваленткниги, и пусть они садятся и выполняют упражнения.Ничто другое не поможет им построить необходимую ментальную модель.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...