VD>По-моему, зачательная демонстрация того, что простые и прямые решения лучше чем эмуляция. И не важно ради чего эта эмуляци делается, из соображений совместимости, или в пылу борьбы за чистоту.

Наш Вычислительный Центр продолжает исследования в области уточнения значений замечательных чисел. Очередной прорыв достигнут при помощи нового суперкомпьютера для точного вычисления единицы по формуле sin^2(x) + cos^2(x): теперь мы знаем, что среди первых тридцати миллионов знаков десятичного разложения нет отличных от нуля.
Это существенный прогресс по сравнению с предыдущим значением в миллион знаков. Зарубежные ученые встретили наши достижения завистливой критикой. "Вы страдаете &$%%!@ней", заявил профессор А. из НьюПорта, "которая не имеет никакого практического применения", а франзузский математик П. не замедлил ехидно поинтересоваться выбором числа x для вычислений и влиянием его точности на результаты.
На это наши ученые отвечают, не теряя достоинства:
Что касается выбора числа X, то в еще в прошлом году в Вестнике РАН уважаемый директор нашего ВЦ опубликовал статью, в которой полностью обосновал наш выбор. Полезность же наших работ может недооценить только человек, абсолютно не знакомый с наукой. Единица используется в огромном количестве теорем; в частности, новые результаты в очередной раз подтвердили основания теории функций комплексного переменного, обосновав принятое приближение для числа i = sqrt(-1) и окончательно похоронили ревизионистские поползновения империалистической науки.

1.2.0 alpha rev. 655

variant Value
    | Error { lst : list[string * Term] }
    | Num { value : int }
    | Fun { f : Value->Value }

    public override ToString() : string
        match(this)
            | Num(value) => value.ToString()
            | Fun(_) => "<function>"
            | Error(lst) => $"<$(lst.Length) error(s)>"

variant Term
    | Var { name : string }
    | Constant { value : int }
    | Add { l : Term; r : Term }
    | Lambda { name : string; expr : Term }
    | Apply { l : Term; r : Term }

    public Eval(environment : list[string * Value]) : Value
        def eval(x) : Value { x.Eval(environment) }

        def errors(lst)
            Value.Error($[e | (errs is Value.Error) in lst, e in errs.lst])

        match(this)
            | Var(name) => match(environment.Find((n, _) => n == name))
                | Some((_, value)) => value
                | None => Value.Error([($"unbound variable : $name", this)])

            | Add(l, r) => match((eval(l), eval(r)))
                | (Num(x), Num(y)) => Value.Num(x + y)
                | (x, y) => errors([x, y, Value.Error([($"should be numbers : $l, $r", this)])])

            | Apply(l, r) => match(eval(l))
                | Fun(f) => f(eval(r))
                | v => errors([v, eval(r), Value.Error([($"should be a function : $l", this)])])

            | Lambda(name, expr) => Value.Fun(param => expr.Eval((name, param) :: environment))

            | Constant(value) => Value.Num(value)

    public override ToString() : string
        match(this)
            | Var(name) => $"var($name)"
            | Constant(value) => $"$value"
            | Add(l,r) => $"$l + $r"
            | Lambda(name, expr) => $"(\\$name -> $expr)"
            | Apply(l, r) => $"$l $$ $r"

// весь этот код в отдельном файле
using System.Console
using Nemerle.Collections
// это чтобы упростить создание ast вручную
using Term

def test(term : Term, locations)
    def value = term.Eval([])
    WriteLine($"'$term' evaluates to $value.")
    // если были ошибки, вывести их расшифровку
    match(term.Eval([]))
        | Error(lst) => 
            foreach((msg, term) in lst)
                WriteLine($"Error : $(locations.GetValueOrDefault(term, -1)) : $msg")
        | _ => ()

def term1 = Apply(Constant(0), Var("x"))
// имхо незачем замусоривать ast локациями, пусть они будут отдельно
def locations = Hashtable()
// добавим локации веток ast в исходном тексте выражения "0 $ x"
// конечно это должно делаться в парсере
match(term1)
    | Apply(_, Var as l4) as l2 =>
        locations.Add(l2 : Term, 2)
        locations.Add(l4, 4)
    | _ => ()

test(term1, locations)
// (\y -> (\x -> x + x) $ y) $ 1
def term2 = Apply(Lambda("y", Apply(Lambda("x", Add(Var("x"), Var("x"))), Var("y"))), Constant(1))
test(term2, locations)

'0 $ var(x)' evaluates to <2 error(s)>.
Error : 4 : unbound variable : x
Error : 2 : should be a function : 0
'(\y -> (\x -> var(x) + var(x)) $ var(y)) $ 1' evaluates to 2.

using System.Console
using Nemerle.Collections
using Nemerle.Utility

variant Value
    | Num { value : int }
    | Fun { f : Value->Value }

variant Term
    | Var { name : string }
    | Constant { value : int }
    | Add { l : Term; r : Term }
    | Lambda { name : string; expr : Term }
    | Apply { l : Term; r : Term }

    [Record] public class EvalException : System.Exception
        [Accessor] description : string
        [Accessor] term : Term

    public Eval(environment : list[string * Value]) : Value
        def eval(x) : Value { x.Eval(environment) }
        match(this)
            | Var(name) => match(environment.Find((n, _) => n == name))
                | Some((_, value)) => value
                | None => throw EvalException($"unbound variable : $name", this)

            | Add(l, r) => match((eval(l),eval(r)))
                | (Num(x), Num(y)) => Value.Num(x + y)
                | _ => throw EvalException($"should be numbers : $l, $r", this)

            | Apply(l, r) => match((eval(l),eval(r)))
                | (Fun(f), p) => f(p)
                | _ => throw EvalException($"should be a function : $l", this)

            | Lambda(name, expr) => Value.Fun(param => expr.Eval((name, param) :: environment))
            | Constant(value) => Value.Num(value)

def term = Term.Apply(Term.Constant(0), Term.Var("x"))

def locations = Hashtable()

match(term)
    | Apply(_, Var as l4) as l2 =>
        locations.Add(l2 : Term, 2)
        locations.Add(l4, 4)
    | _ => ()

try
    WriteLine(term.Eval([]))
catch
    | err is Term.EvalException =>
        def location = locations.GetValueOrDefault(err.Term, -1)
        WriteLine($"Error : $location : $(err.Description)")

cartesian3 :: [a]->[b]->[c]->[(a,b,c)]
cartesian3 = liftM3 (,,)

LCR>_solve :: Matrix Int -> Vector Int -> Vector Int
LCR>_solve m b = -- далее идёт метод решения СЛАУ с матрицей m и правым столбцом b скажем методом LU
LCR>             -- разложения, здесь можно использовать традиционный доступ к мутабельным массивам, 
LCR>             -- циклы и т.п.
LCR>                         -- компилятор рассматривает эту функцию как неделимую сущность

LCR>main :: IO () -> ()
LCR>main = do
LCR>    (m, b) <- loadSLAE("slae.txt")
LCR>    putStrLn (show $ _solve m b)
LCR>

f :: Int -> Int
f a = runST (do x <- newSTRef a
                modifySTRef x (*2)
                readIORef x
            )

Most programming languages are rooted in the lambda calculus, which provides the basic mechanisms for procedural abstraction and procedure (subprogram) application.

The most prominent counterparts to lambda calculus in programming are functional programming languages, which essentially implement the calculus augmented with some constants and datatypes.

The first order of business was to establish the following goals for the language:
1. It should be suitable for teaching, research, and applications, including building large systems.
2. It should be completely described via the publication of a formal syntax and semantics.
3. It should be freely available. Anyone should be permitted to implement the language and distribute it to whomever they please.
4. It should be usable as a basis for further language research.
5. It should be based on ideas that enjoy a wide consensus.
6. It should reduce unnecessary diversity in functional programming languages. More specifically, we initially agreed to base it on an existing language, namely OL.

In mathematics and computer science, higher-order functions or functionals are functions which do at least one of the following:

* take one or more functions as an input
* output a function

In computer science, a programming language is said to support first-class functions if it treats functions as first-class objects. Specifically, this means that functions can be created during the execution of a program, stored in data structures, passed as arguments to other functions, and returned as the values of other functions.

The modern, natively compiled programming languages support functions defined statically at compile time. Most of them, e.g. C and Pascal, additionally support function pointers, which can be stored in data structures and passed as arguments to other functions. Nevertheless, they are not considered to support first class functions, since, in general, functions cannot be created dynamically during the execution of a program. The closest analog would be a dynamically compiled function created by a just-in-time compiler, which is compiled as an array of machine language instructions in memory and then cast to a function pointer. However, this technique is specific to the underlying hardware architecture and is, therefore, neither general nor portable.

VD>>Казалось бы. Пометь блок кода и скажи, что он должен выполняться последовательно и не лениво. И все! Пиши себе в других местах пользуясь всеми приемуществами линивости, а когда надо просто переключайся в императив. Но нет, мы создаем себе сказку и усилиенно пытаемся поверить в нее. В итоге получаем тоже самое, но сложно, запутано и медленно.

BZ>f x = let y = x*2
BZ>          z = y+3
BZ>      in y*z
BZ>

_solve :: Matrix Int -> Vector Int -> Vector Int
_solve m b = -- далее идёт метод решения СЛАУ с матрицей m и правым столбцом b скажем методом LU
             -- разложения, здесь можно использовать традиционный доступ к мутабельным массивам, 
             -- циклы и т.п.
                         -- компилятор рассматривает эту функцию как неделимую сущность

main :: IO () -> ()
main = do
    (m, b) <- loadSLAE("slae.txt")
    putStrLn (show $ _solve m b)

do x <- get
   put (x + 2)
   return x

As many of you will be aware, C#3.0 is adding a significant number of new language features. While the overall driving force behind putting these features in is the support of LINQ (Language INtegrated Query), the way we do it is strongly inspired by functional programming techniques. Moreover, we strive to make the new features as general-purpose as possible (with the exception of query expressions – they are undeniably tied to the querying domain!), so they do come out as features that will enable more of a functional style of programming.

This begs the question: Are we making C# a functional language?

This of course is a vague question. First of all, what exactly is a functional programming language? What does it take to qualify? Rather than trying to define the canonical list of language features that you have to have to be functional, I think it makes more sense to define it as “a language that supports a functional style of programming.”

....

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

-- Имена переменных описываются строкой
type Name   = String

-- Термом может быть
--      Переменная
data Term   = Var Name
--    Константа
    | Constant Int
--    Операция сложения
    | Add Term Term
--    Лямбда
    | Lambda Name Term
--    Операция вычисления
    | Apply Term Term

-- Значением может быть 
--    Ошибка
data Value = Wrong
--    Число
    | Num Int
--    Функция (Functions are first class values :super:)
    | Fun (Value -> M Value)

-- Environment - это переменные окружения, представленные списком пар (Имя, Значение)
type Environment = [(Name, Value)]

-- Функция вывода значения 
showVal   :: Value -> String
showVal Wrong = "<wrong>"
-- Для вывода числовых значений используется функция show из стандартной библиотеки Prelude
showVal (Num i)  = show i
showVal (Fun f) = "function"

-- Ключевая функция - интерпретатор. 
interprete      ::  Term -> Environment -> M Value
-- Интерпретация значения переменной "x"  сводится к поиску значения в переменных окружения 
interprete (Var x) environment    =   searchFor x environment
-- Интерпретация константы производится путем возврата монадического значения числа.
-- то есть берем число "i" представляющее константу и запихиваем его в монаду при промощи функции
-- returnM имеющую тип a -> M a
interprete (Constant i) environment     =   returnM (Num i)

-- Интерпретация операции сложения. Запись более развернутая чем у Вадлера в целях упрощения понимания
-- удобнее рассматривать производящее с конца.
-- возьмем функцию add a b она вернет нам M Value согласно ее типу
-- то есть тип лямбды (\b -> add a b) будет Value -> M Value
-- поднимаемся на строчку выше и рассматриваем строку
-- bindM y_value (Value -> M Value)
-- поскольку bindM имеет тип  M a -> (a - M b) -> M b
-- то y_value будет иметь тип M Value , поскольку такой тип у функции interprete, резульаттом работы которой и является y_value
-- а все выражение будет иметь тип bindM M Value (Value -> M Value)
-- то есть просто M Value, а значеним его будет M x+y , то есть сумма чисел x и у, будет внутри монады
-- После упрощения остается bindM x_value (\a -> M x+y)
-- значением лябмды будет M x+y, а ее типом - (Value -> M Value)
-- Следовательно результатом функции interprete (Add x y) е будет значение суммы x+y завернутое в монаду.
interprete (Add x y) environment  =   bindM x_value  
            (\a -> 
              bindM y_value  
              (\b -> add a b))
            where 
              x_value = (interprete x environment)        
              y_value = (interprete y environment)

-- Интерпретация применения функции к аргументу.  Абсолютно идентична Add x y_value
-- за исключеним того, что возвращаемым значением будет M apply a b
interprete (Apply function argument) environment  = bindM function_value  
            (\a -> 
              bindM argument_value  
              (\b -> apply a b))
            where 
              function_value = (interprete function environment)        
              argument_value = (interprete argument environment)

-- Интерпретация лямбды. 
-- Значением выражения будет функция Fun 
-- Согласно конструктору типа Fun принимает значение (Value -> M Value)
-- Проверим, так ли это. Расмотрим выражение (\a -> interprete v ((x,a):environment)) 3
-- подставив неопсредственно значение 3 в лямбду получим
-- interprete v ((x,3):environment)
-- таким образом зачением лямбды будет выражение v  вычисленное в окружении, в  котором х имеет непосредственно значение.
-- иначе говоря сначла мы добавляем в спиоск окружения новую переменную х, а потом вычилсяем значения лямбды
-- как interprete v new_environment, где new_environment = ((x,3):environment)
interprete (Lambda x v) environment   =   returnM (Fun (\a -> interprete v ((x,a) : environment)))

-- Функция поиска значения переменной в окружении
-- Классический рекурсивный проход по списку. Если значение найдено, возврщается монадическое значение переменной, 
-- иначе Wrong
searchFor       :: Name -> Environment -> M Value
-- Если добрались до конца спписка или окружение пусто - ошибка
searchFor x []    = returnM Wrong
-- Если имя "х" и имя первой пары в списке окружения "у" равны
searchFor x ((y,b) : environment) = if x ==y 
          -- то возвращаем значене
          then returnM b 
          -- иначе продолжим поиск в остальной части списка
          else searchFor x environment

-- Функция сложения
add       :: Value -> Value -> M Value
-- если параметрами являются два числовых значения, то возвращаем монадическое значение их суммы
add (Num x) (Num y) = returnM (Num (x+y))
-- иначе возвращаем ошибку
add x y       = returnM Wrong

-- Применение функции к аргументу
apply       :: Value -> Value -> M Value
-- Если первый агрумент функция, то результатом будет применение функции f к аргументу а
apply (Fun function) argument     = function argument
-- Иначе возвращаем ошибку
apply function argument     = returnM Wrong

-- Функция test используется для вывода на экран значения терма.
test        :: Term -> String
-- Интерпретируем терм в пустом окружении, что даст на выходе M Value, и передаем результат в функцию
-- showM, которая имеет тип M Value -> String
test term       = showM (interprete term [])

-- тестовый терм для проверки вычиления значения лябмда-выражения
--  (lambda x ( x + x))( 10 + 11) = 42
-- проверка производится  в интерпретаторе Haskell путем вызова 
--Main> test term0
--"42"
term0 = (Apply  (Lambda "x" (Add (Var "x") (Var "x")))
      (Add (Constant 10) (Constant 11)))
      
-- тест который должен возвратить значение типа "функция"
term1 = (Lambda "x" (Add (Var "x") (Var "x")))

calculate = withState $ do
                calc1
                x <- calc2
                y <- calc3
                return (x++y)

calc1 = put (1, 2.3, "рояль")

calc2 = do (a,b,c) <- get
           put (4, 5.6, " в кустах")
           return c

calc3 = do (a,b,c) <- get
           return c

calculate = withState $ \state0 ->
                let (state1,_) = calc1 state0
                    (state2,x) = calc2 state1
                    (state3,y) = calc3 state2
                in (x++y)

calculate = withEnvironment $ env ->
                let _ = calc1 env
                    x = calc2 env
                    y = calc3 env
                in (x++y)

class  Enum a  where
    succ, pred     :: a -> a
    toEnum         :: Int -> a
    fromEnum       :: a -> Int
    enumFrom       :: a -> [a]            -- [n..]
    enumFromThen   :: a -> a -> [a]       -- [n,n'..]
    enumFromTo     :: a -> a -> [a]       -- [n..m]
    enumFromThenTo :: a -> a -> a -> [a]  -- [n,n'..m]

class  Bounded a  where
    minBound, maxBound :: a

И Остап протянул Ухудшанскому лист, на котором было
написано: ТОРЖЕСТВЕННЫЙ КОМПЛЕКТ НЕЗАМЕНИМОЕ ПОСОБИЕ ДЛЯ СОЧИНЕНИЯ ЮБИЛЕЙНЫХ СТАТЕЙ, ТАБЕЛЬНЫХ ФЕЛЬЕТОНОВ, А ТАКЖЕ ПАРАДНЫХ СТИХОТВОРЕНИЙ. ОД И ТРОПАРЕЙ.

0   start: p := 0;
1          i := n;
2   loop:  if i = 0 then go to done;
3          p := p + m;
4          i := i - 1;
5          go to loop;
6   done:

  p(t+1) = if pc(t) = 0 then 0
           else if pc(t) = 3 then p(t) + m
           else p(t),

  i(t+1) = if pc(t) = 1 then n
           else if pc(t) = 4 then i(t) - 1
           else i(t),

  pc(t+1) = if pc(t) = 2 & i(t) = 0 then 6
            else if pc(t) = 5 then 2
            else p(t) + 1.

fac 0 = 1
fac 1 = n * fac(n-1)

fac n = foldr (*) [1..n]

BZ>а это не для начинающих для начала удобно как раз считать, что в хаскеле есть императивный и функциональный подязыки. я даже собирался написать "introduction to IO" в этом ключе, без всяких упоминаний о монадах. может, напишу его на русском

BZ>всякая концепция, которую ты уже понял, кажется простой для понимания скажем, я считаю функциональный подход более естественным и простым для понимания, нежели императивный

BZ>fac 0 = 1
BZ>fac 1 = n * fac(n-1)
BZ>

fac(int n)
{
  if (n == 0)
      return 1;
    else
      return n * fac(n - 1);
}

BZ>fac n = foldr (*) [1..n]
BZ>

struct EnhancedFunctor
{
    struct Functor base; //Трюк с наследованием
    int threshold;
};

int sumNumbersGreaterThan(Functor *self, int a, int b)
{
    EnhancedFunctor *enh=(EnhancedFunctor*)self; //!!
    if (a>enh->threshold) return b;
    return b+a;
}

//Наш конструктор
Functor * new_filtering_functor(int threshold)
{
    EnhancedFunctor *f=(EnhancedFunctor*)malloc(sizeof(Functor));
    f->base.func=&sumNumbersGreaterThan;
    f->threshold=threshold;
    return f;
}

//Немного модифицируем reduce:
int reduce(List *lst, Functor *f)
{
     int res=0;
     while(lst!=null)
     {
         res=f->func(f, lst->data,res); //Добавим указатель 'this'
         lst=lst->next;
     }
     return res;
}

...
Functor *filter=new_filtering_functor(11);
int res=reduce(some_list, filter);

[ (x,y,z) | x<-[1..n], y<-[x..n], z<-[y..n], x^2+y^2==z^2 ]

triangles n = do x<-[1..n]
                 y<-[x..n]
                 z<-[y..n]
                 guard$ x^2+y^2==z^2
                 return (x,y,z)

VD>Ответы про монады, как сами монады — аморфны и выскальзают из рук. Никогда не получишь прямого и однозначного ответа.

instance Monad [] where
    m >>= f  = concatMap f m
    return x = [x]
    fail s   = []

List> concatMap (replicate 2) [1..5]
[1,1,2,2,3,3,4,4,5,5]

public class List : IMonad
    // грубо говоря делаем map функции f на список
    public IMonad.Bind(m, f)
    {
        ConcateMap(f, m)
    }
    // оборачиваем X любого типа в список. Теперь Х просто так не достать. 
    //Он спрятан внутри монады (или класса List)
    //и доступ к нему возможен только через интерфейсы, 
    //поддерживаемые классом List. В нашем случае это только IMonad
    public IMonad.Return(x);
    {
        return new List(x);
    }
// А здесь просто возвращаем пустой список.
    public IMonad.Fail(s)
    {
        return new List();
    }

In programming three important perspectives are:
— Function oriented programming: The computing process is viewed as a sequence of applications of functions to an input, producing an output, that in its turn may be the input to another functions etc.
— Object oriented programming: The computing process is viewed (as described above) as the development of a system, consisting of objects (components), through sequences of changing states.
— Constraint oriented programming: The computing process is viewed as a deduction process, developing from an initial state, the process being restricted by sets of constraints and inputs from the environment, information about the states being deduced by an inferencing algorithm. Logic programming using first order predicate logic is currently the most important example (Prolog).
It seems obvious to the author that all these three perspectives should be supported within any new general programming language in the future. No perspective will "win" as some seem to believe.

In mathematics and computer science, higher-order functions or functionals are functions which do at least one of the following:

* take one or more functions as an input
* output a function

Fun3=fun(Fun1,Fun2)-> Fun1() + Fun2() end.

Р. В. Душкин "Функциональное программирование на языке Haskell"

Автор(ы): Р. В. Душкин
Издательство: ДМК пресс
Цена: 314р.

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

Монада — это контейнерный тип данных, который представляет собой экземпляр класса Monad,
так же это экземпляр класса Functor, который декларирует наличие одной функции высшего порядка, преобразующей значения в контейнере в соответствии с некоторой функцией.

BZ>и >>= будет стратегией вычислений, формирующей из отдельных вызовов выполняемый оператор sql. в linq, вероятно, точно так же

xs.Where(x => x > 3).OrderBy(x).Select(x => new { x.a, x, b })