Функции высшего порядка

@Denndi · Регистрация: 26.01.2016

Author24 — интернет-сервис помощи студентам

Доброго времени суток.
Нужна помощь в решении задачи.

Определить функцию высшего порядка reduce2 (G,X,A), применение которой к списку одноразрядных целых чисел x=(x1 x2 … xk) выдает значение (g … (g (g a x1) x2) … xk). Например,
> Reduce2 (fun(Y,Z)-> (10*Y+Z) end, [1,2,3],0).
123 ; результат – число

@Curry · 18.06.2016, 11:08

Это называется левая свёртка, только по отношению к библиотечной lists:foldl аргументы переставлены

Prolog

-module(foo_module).
 
-export([reduce2/3]).
 
reduce2(_,[],A) -> A; 
reduce2(F,[X|XS],A) -> reduce2(fun(Y,Z)-> F(Y,Z) end, XS, F(A,X)).

@Denndi · 18.06.2016, 15:00 **[ТС]**

Вновь выручили, большое спасибо.

@Denndi · 22.12.2016, 12:13 **[ТС]**

Здравствуйте, не могли бы вы подробнее раскрыть значение последних двух строк.
Объяснить что такое левая свертка и почему переставлены аргументы.
Буду очень благодарен

@Curry · 22.12.2016, 13:08

Сообщение от Denndi

не могли бы вы подробнее раскрыть значение последних двух строк

Строка 5: если второй аргумент - список, пуст ([]), то возвращаем A. Этот вариант выполнится последним, когда список закончится.
Строка 6: (выполняется, если предыдущий вариант не подошёл, т.е. список не пуст) выделяем в списке первый элемент X и остаток списка XS, вызываем эту же функцию (рекурсия). Аргументы: та же функция F, остаток списка XS, результат выполнения функции F который станет новым значением A в следующей рекурсии.
http://learnyousomeerlang.com/... -functions

Книги: Чезарини Ф. Томпсон С. Программирование в Erlang
Бьярн Дэкер, Роберт Вирдинг Настольная книга по Erlang
Learn You Some Erlang for Great Good! (Изучай Erlang во имя добра!) Frederic Trottier-Hebert
- гуглите. Или на торрентах берите. Или покупайте. Всё есть.

Сообщение от Denndi

что такое левая свертка

Левоассоциативная свёртка списка..

Сообщение от Denndi

почему переставлены аргументы

потому что так в вашем задании. Существует уже готовая библиотечная функция, делающая то же самое, но у неё другая последовательность аргументов.

@Denndi · 23.12.2016, 18:48 **[ТС]**

Здравствуйте, пытаясь разобраться в вашем ответе возникли некоторые вопросы.
Шестая строка начинается с функции свертки F которая вычисляет в списке первый элемент X и остаток XS.
Вызывая эту же функцию (рекурсию reduce2) не понимаю что происходит при добавлении безымянной функции fun(Y,Z).
Пожалуйста объясните, что они означают?
Или X это Y и XS является Z?
Тогда мы в нашей новорекурсивно-безымянной функцией fun (Y,Z) вводим значения? какие? [1,2,3]?
Далее мы по моему предположению вызываем нами введенные данные в функции свертки F?
Остаток списка XS.
Получается остаток списка является [2,3]?
F(A,X)- результат выполнения функции F который станет новым значением A в следующей рекурсии.
Получается мы "прогнали" нашу рекурсию и оставшаяся последняя голова X нашего списка становится новым значением A?

Левая свертка
В моем примере (g … (g (g a x1) x2) … xk) равно как и в примере википедии (f ... (f (f start elem_1) elem_2) ... elem_n) я разобрался (Спасибо)
в следующей ссылке
lists:foldl(fun(X, Sum) -> X + Sum end, 0, [1,2,3,4,5]) (как левоассоциативная свертка) аналогична моему примеру reduce2(fun(Y,Z)-> F(Y,Z) end, XS, F(A,X)). В чем проявляется изменение аргументов.
Спасибо.

@Curry · 23.12.2016, 19:42

Denndi, дальше вам необходимо читать учебник. С начала. Объяснять конкретный пример стоит когда в нём немного не понятно. А вам непонятно всё. И с терминологией завал. "что происходит при добавлении безымянной функции". Никакого добавления нет. Есть передача анонимной функции в качестве первого аргумента.

@FateOri · 08.01.2017, 23:55

KolodeznyDiver, попытался написать решение на Elixir проверьте пожалуйста

Код

defmodule Recursion do
  def reduce2([], z) do
    z
  end
  def reduce2([h|t], z) do
    reduce2(t, 10*h + z)
  end
end

и еще вопрос : как сделать то-же самое но только с анонимной функцией. Пытался так:

Код

reduce2 = fn 
([],z) -> z 
([h|t],z) -> reduce2(t, 10*h + z)
end

но пишет ошибку

@Curry · 09.01.2017, 02:22

Сообщение от FateOri

проверьте пожалуйста

Вы не написали что оно, по вашему, должно делать. Оно, может и так должно работать. А может вы хотели

Ruby

defmodule Recursion do
  def reduce2([], z) do
    z
  end
  def reduce2([h|t], z) do
    reduce2(t, h + 10*z)
  end
end

Ну, и вы, конечно, знаете что можно записать короче

Ruby

defmodule Recursion do
  def reduce2([], z), do: z
  def reduce2([h|t], z), do: reduce2(t, h + 10*z)
end

И проверка

iex(2)> c("tst1.ex")
[Recursion]
iex(3)> Recursion.reduce2([3,1,4],0)
314

А вот прямой рекурсивный вызов анонимной функции, кажется, ещё не сделали.
Это должно было бы выглядеть как то так (по аналогии с Erlang-ом)

Ruby

reduce2 = fn
   go([],z) -> z
   go([h|t],z) -> go(t, h + 10*z)
end

но, это не откомпилируется (пока?).
Простейший способ сделать рекурсию в анонимной функции - передавать её ей же в аргументе

Ruby

  def reduce3(l,z0) do
    reduce2 = fn
       (f,[],z) -> z
       (f,[h|t],z) ->  f.(f,t,h + 10*z)
    end
    reduce2.(reduce2,l,z0)
  end

Легко гуглится : http://stackoverflow.com/quest... -in-elixir
https://www.reddit.com/r/elixi... in_elixir/
и т.д.

@FateOri · 09.01.2017, 13:46

Сообщение от KolodeznyDiver

Ну, и вы, конечно, знаете что можно записать короче

Спасибо, не знал - второй день как Elixir учу

Сообщение от KolodeznyDiver

но, это не откомпилируется (пока?).

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

Сделал универсальную версию:

Ruby

defmodule Recursion do
  def reduce2(f,[], z) do
    z
  end
  def reduce2(f, [h|t], z) do
    reduce2(f, t, f.(h,z))
  end
end

теперь нормально?

@Curry · 09.01.2017, 14:53

FateOri, Вы сделали левую свёртку, только с другим порядком аргументов, по сравнению с библиотечной

iex(2)> c("tst1.ex")
[Recursion]
iex(3)> Recursion.reduce2(fn (h,z) -> h + 10*z end,[3,1,4],0)
314
iex(4)> List.foldl([3,1,4], 0, fn (h,z) -> h + 10*z end)
314
iex(5)>

Поздравляю с началом освоения функционального программирования!

@FateOri · 09.01.2017, 18:27

Спасибо))
Можно еще спросить где можно найти упражнения для тренировки?

@Curry · 09.01.2017, 20:07

Сообщение от FateOri

где можно найти упражнения для тренировки?

Существует сайт https://www.codewars.com/ . Если с английским хотя бы "читаю статьи по программированию (почти) без словаря", то можно туда. Там, при входе, выберите язык - Elixir есть. Решаете по нему простейшую задачку (обычно найти синтаксическую ошибку), регистрируетесь. Там сейчас 140 задач по нему. Решая их поднимаетесь по мастерству : 9кю - 1кю - 1дан - 9дан. В общем японская система уровней, как в дзюдо и пр. Хотя, сайт, кажется, ни как не японский, просто под это стилизован.
Я когда то в нём по Haskell дошёл до 2кю. Рекомендую. (Надеюсь, не сочтут за рекламу. В разделе Haskell его уже упоминали, и я к его владельцам отношения не имею).

@FateOri · 10.01.2017, 00:01

Сообщение от KolodeznyDiver

Существует сайт https://www.codewars.com/ . Если с английским хотя бы "читаю статьи по программированию (почти) без словаря", то можно туда.

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

Добавлено через 13 минут
KolodeznyDiver, пытаюсь зарегистрироваться - не пускает, спрашивает:

The code does not execute properly. Try to figure out why.

Ruby

defmodule Multiply do
  def multiply(a b) do
    a * b
  end
end

я думал что не компилируется из-за того что не хватает запятой:

Ruby

defmodule Multiply do
  def multiply(a,b) do
    a * b
  end
end

отправляю такой варинт и получаю:

Time: ms Passed: Failed:

может тут что-то другое нужно вводить?

@Curry · 10.01.2017, 01:52

Сообщение от FateOri

Time: ms Passed: Failed:

Дык, долго думали. Надо быстро.

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

@FateOri · 10.01.2017, 11:57

Спасибо теперь все получилось. Мало что понимаю еще но вроде сайт отличный для тренировок

@Denndi 0 / 0 / 0 Регистрация: 26.01.2016 Сообщений: 22
		1
	Функции высшего порядка 18.06.2016, 09:26. Показов 4915. Ответов 15 Метки нет (Все метки) Доброго времени суток. Нужна помощь в решении задачи. Определить функцию высшего порядка reduce2 (G,X,A), применение которой к списку одноразрядных целых чисел x=(x1 x2 … xk) выдает значение (g … (g (g a x1) x2) … xk). Например, > Reduce2 (fun(Y,Z)-> (10*Y+Z) end, [1,2,3],0). 123 ; результат – число 0

@Denndi 0 / 0 / 0 Регистрация: 26.01.2016 Сообщений: 22
	18.06.2016, 15:00 [ТС]	3
	Вновь выручили, большое спасибо. 0

@Denndi 0 / 0 / 0 Регистрация: 26.01.2016 Сообщений: 22
	22.12.2016, 12:13 [ТС]	4
	Здравствуйте, не могли бы вы подробнее раскрыть значение последних двух строк. Объяснить что такое левая свертка и почему переставлены аргументы. Буду очень благодарен 0

@Curry Модератор 5047 / 3276 / 526 Регистрация: 01.06.2013 Сообщений: 6,806 Записей в блоге: 9
	22.12.2016, 13:08	5
	Сообщение от Denndi не могли бы вы подробнее раскрыть значение последних двух строк Строка 5: если второй аргумент - список, пуст ([]), то возвращаем A. Этот вариант выполнится последним, когда список закончится. Строка 6: (выполняется, если предыдущий вариант не подошёл, т.е. список не пуст) выделяем в списке первый элемент X и остаток списка XS, вызываем эту же функцию (рекурсия). Аргументы: та же функция F, остаток списка XS, результат выполнения функции F который станет новым значением A в следующей рекурсии. http://learnyousomeerlang.com/... -functions Книги: Чезарини Ф. Томпсон С. Программирование в Erlang Бьярн Дэкер, Роберт Вирдинг Настольная книга по Erlang Learn You Some Erlang for Great Good! (Изучай Erlang во имя добра!) Frederic Trottier-Hebert - гуглите. Или на торрентах берите. Или покупайте. Всё есть. Сообщение от Denndi что такое левая свертка Левоассоциативная свёртка списка.. Сообщение от Denndi почему переставлены аргументы потому что так в вашем задании. Существует уже готовая библиотечная функция, делающая то же самое, но у неё другая последовательность аргументов. 2

@Denndi 0 / 0 / 0 Регистрация: 26.01.2016 Сообщений: 22
	23.12.2016, 18:48 [ТС]	6
	Здравствуйте, пытаясь разобраться в вашем ответе возникли некоторые вопросы. Шестая строка начинается с функции свертки F которая вычисляет в списке первый элемент X и остаток XS. Вызывая эту же функцию (рекурсию reduce2) не понимаю что происходит при добавлении безымянной функции fun(Y,Z). Пожалуйста объясните, что они означают? Или X это Y и XS является Z? Тогда мы в нашей новорекурсивно-безымянной функцией fun (Y,Z) вводим значения? какие? [1,2,3]? Далее мы по моему предположению вызываем нами введенные данные в функции свертки F? Остаток списка XS. Получается остаток списка является [2,3]? F(A,X)- результат выполнения функции F который станет новым значением A в следующей рекурсии. Получается мы "прогнали" нашу рекурсию и оставшаяся последняя голова X нашего списка становится новым значением A? Левая свертка В моем примере (g … (g (g a x1) x2) … xk) равно как и в примере википедии (f ... (f (f start elem_1) elem_2) ... elem_n) я разобрался (Спасибо) в следующей ссылке lists:foldl(fun(X, Sum) -> X + Sum end, 0, [1,2,3,4,5]) (как левоассоциативная свертка) аналогична моему примеру reduce2(fun(Y,Z)-> F(Y,Z) end, XS, F(A,X)). В чем проявляется изменение аргументов. Спасибо. 0

@Curry Модератор 5047 / 3276 / 526 Регистрация: 01.06.2013 Сообщений: 6,806 Записей в блоге: 9
	23.12.2016, 19:42	7
	Denndi, дальше вам необходимо читать учебник. С начала. Объяснять конкретный пример стоит когда в нём немного не понятно. А вам непонятно всё. И с терминологией завал. "что происходит при добавлении безымянной функции". Никакого добавления нет. Есть передача анонимной функции в качестве первого аргумента. 1

@FateOri Фрилансер 761 / 458 / 146 Регистрация: 06.01.2017 Сообщений: 4,856
	08.01.2017, 23:55	8
	KolodeznyDiver, попытался написать решение на Elixir проверьте пожалуйста Код defmodule Recursion do def reduce2([], z) do z end def reduce2([h\|t], z) do reduce2(t, 10h + z) end end и еще вопрос : как сделать то-же самое но только с анонимной функцией. Пытался так: Код reduce2 = fn ([],z) -> z ([h\|t],z) -> reduce2(t, 10h + z) end но пишет ошибку 0

@Curry Модератор 5047 / 3276 / 526 Регистрация: 01.06.2013 Сообщений: 6,806 Записей в блоге: 9
	09.01.2017, 14:53	11
	FateOri, Вы сделали левую свёртку, только с другим порядком аргументов, по сравнению с библиотечной iex(2)> c("tst1.ex") [Recursion] iex(3)> Recursion.reduce2(fn (h,z) -> h + 10z end,[3,1,4],0) 314 iex(4)> List.foldl([3,1,4], 0, fn (h,z) -> h + 10z end) 314 iex(5)> Поздравляю с началом освоения функционального программирования! 1

@FateOri Фрилансер 761 / 458 / 146 Регистрация: 06.01.2017 Сообщений: 4,856
	09.01.2017, 18:27	12
	Спасибо)) Можно еще спросить где можно найти упражнения для тренировки? 0

@Curry Модератор 5047 / 3276 / 526 Регистрация: 01.06.2013 Сообщений: 6,806 Записей в блоге: 9
	09.01.2017, 20:07	13
	Сообщение от FateOri где можно найти упражнения для тренировки? Существует сайт https://www.codewars.com/ . Если с английским хотя бы "читаю статьи по программированию (почти) без словаря", то можно туда. Там, при входе, выберите язык - Elixir есть. Решаете по нему простейшую задачку (обычно найти синтаксическую ошибку), регистрируетесь. Там сейчас 140 задач по нему. Решая их поднимаетесь по мастерству : 9кю - 1кю - 1дан - 9дан. В общем японская система уровней, как в дзюдо и пр. Хотя, сайт, кажется, ни как не японский, просто под это стилизован. Я когда то в нём по Haskell дошёл до 2кю. Рекомендую. (Надеюсь, не сочтут за рекламу. В разделе Haskell его уже упоминали, и я к его владельцам отношения не имею). 1

@Curry Модератор 5047 / 3276 / 526 Регистрация: 01.06.2013 Сообщений: 6,806 Записей в блоге: 9
	10.01.2017, 01:52	15
	Сообщение от FateOri Time: ms Passed: Failed: Дык, долго думали. Надо быстро. Задачки потом можно сколько угодно решать. Вот по скорости выполнения ограничения будут. 1

@FateOri Фрилансер 761 / 458 / 146 Регистрация: 06.01.2017 Сообщений: 4,856
	10.01.2017, 11:57	16
	Спасибо теперь все получилось. Мало что понимаю еще но вроде сайт отличный для тренировок 0

Функции высшего порядка

Решение