Теория-практика: накопление суммы в "чисто" функциональных ЯП

@Slenon · Регистрация: 25.07.2016

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

Согласно теории, в Haskell, как и в ему подобных ЯП, конструкция S = S + A[i] (где то так...) не может работать!
Т.Е. есть проблема как осуществить накопление суммы...
Я думаю о следующем - создаётся список нулевой длины и ему раз за разом присваивается значение функции
находящейся в "цикле", после его окончания получившийся список, точнее его элементы, суммируются и таким
образом мы обходим "проблему суммирования"...

Tklwegsd · 02.03.2017, 17:05

Решите сначала последнию задачу, найдите сумму элементов списка.
Возможно, первая задача у Вас решится сама собой по аналогии.

@_Ivana · 02.03.2017, 17:06

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

Т.Е. есть проблема

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

@Catstail · 02.03.2017, 17:59

Суммировать массив без сакраментального "s=s+a[i]" можно в любом языке. Например, вот два варианта, как это может выглядеть в C/С++:

C

int sum_arr_1(int *Arr, int n) // простая рекурсия
{
    return (n==0)?0:Arr[0]+sum_arr_1(Arr+1,n-1);
}          
 
int sum_arr_2(int *Arr, int n,int s) // хвостовая рекурсия с накопительным 
                                              // параметром
{
    return (n==0)?s:sum_arr_2(Arr+1,n-1,s+Arr[0]);
}

Соответственно, в Haskell это может выглядеть так:

Haskell

sum_list_1 [] = 0
sum_list_1 (x:xs) = x + sum_list_1 xs
 
sum_list_2 [] acc = acc
sum_list_2 (x:xs) acc = sum_list_2 xs (acc+x)

Добавлено через 1 минуту
Но проще, конечно, вот так:

Haskell

1	sum_list = sum

@~~oopguru~~ · 04.03.2017, 11:58

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

Согласно теории, в Haskell, как и в ему подобных ЯП, конструкция S = S + A[i] (где то так...) не может работать!
Т.Е. есть проблема как осуществить накопление суммы...

Никак. Накопление невозможно уже потому, что невозможно состояние.
Можно имитировать это. То есть условно считать, что каждая последующая новая сумма является "тем же самым аккумулятором". Но "считать" так может только внешний наблюдатель, на уровне семантики ФП это абстрагировать невозможно

Добавлено через 24 минуты
Кстати, если интересует, какие еще ограничения имеются в ФП, помимо абстракции состояния и времени -- это конкурентрые вычисления. Они тоже не могут быть описаны в рамках семантики ФП.

Например, пусть у нас есть выражение foo(bar). Если это выражение выполняется конкурентно, то очевидно, что нам нужны механизмы синхронизации, поскольку foo не может быть вычисленно до тех пор, пока не вычесленно bar. То есть, нам нужно что то-вроде того, что после запуска этого выражения, сначала ставится задача на вычисление bar, а пока оно вычисляется (и одновременно с этим вычисляется другой код) foo "ждет" результат этого вычисления. Однако, в семантике чистого ФП нет никаких определений для описания механизмов такой синхронизации(futures etc). Впрочем, если бы эти определения были, было бы странно, так как мы были бы вынужденны ввести понятие "время"

@Curry · 04.03.2017, 12:37

Не по теме:

аха, история, опять, продолжается

@~~oopguru~~ · 04.03.2017, 13:24

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

Я думаю о следующем - создаётся список нулевой длины и ему раз за разом присваивается значение функции
находящейся в "цикле", после его окончания получившийся список, точнее его элементы, суммируются и таким
образом мы обходим "проблему суммирования"...

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

@Slenon 5 / 5 / 3 Регистрация: 25.07.2016 Сообщений: 182
		1
	Теория-практика: накопление суммы в "чисто" функциональных ЯП 02.03.2017, 16:44. Показов 1324. Ответов 6 Метки нет (Все метки) Согласно теории, в Haskell, как и в ему подобных ЯП, конструкция S = S + A[i] (где то так...) не может работать! Т.Е. есть проблема как осуществить накопление суммы... Я думаю о следующем - создаётся список нулевой длины и ему раз за разом присваивается значение функции находящейся в "цикле", после его окончания получившийся список, точнее его элементы, суммируются и таким образом мы обходим "проблему суммирования"... 0

Tklwegsd 843 / 606 / 211 Регистрация: 24.07.2013 Сообщений: 2,102
	02.03.2017, 17:05	2
	Решите сначала последнию задачу, найдите сумму элементов списка. Возможно, первая задача у Вас решится сама собой по аналогии. 2

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	02.03.2017, 17:06	3
	Сообщение от Slenon Т.Е. есть проблема Никаких проблем нет. Для начала попробуйте просуммировать несколько значений без деструктивного присваивания, написав кота на любом известном вам языке. 2

@~~oopguru~~ Заблокирован
	04.03.2017, 11:58	5
	Сообщение от Slenon Согласно теории, в Haskell, как и в ему подобных ЯП, конструкция S = S + A[i] (где то так...) не может работать! Т.Е. есть проблема как осуществить накопление суммы... Никак. Накопление невозможно уже потому, что невозможно состояние. Можно имитировать это. То есть условно считать, что каждая последующая новая сумма является "тем же самым аккумулятором". Но "считать" так может только внешний наблюдатель, на уровне семантики ФП это абстрагировать невозможно Добавлено через 24 минуты Кстати, если интересует, какие еще ограничения имеются в ФП, помимо абстракции состояния и времени -- это конкурентрые вычисления. Они тоже не могут быть описаны в рамках семантики ФП. Например, пусть у нас есть выражение foo(bar). Если это выражение выполняется конкурентно, то очевидно, что нам нужны механизмы синхронизации, поскольку foo не может быть вычисленно до тех пор, пока не вычесленно bar. То есть, нам нужно что то-вроде того, что после запуска этого выражения, сначала ставится задача на вычисление bar, а пока оно вычисляется (и одновременно с этим вычисляется другой код) foo "ждет" результат этого вычисления. Однако, в семантике чистого ФП нет никаких определений для описания механизмов такой синхронизации(futures etc). Впрочем, если бы эти определения были, было бы странно, так как мы были бы вынужденны ввести понятие "время" 0

@Curry
	04.03.2017, 12:37 #6
	Не по теме: аха, история, опять, продолжается 0

@~~oopguru~~ Заблокирован
	04.03.2017, 13:24	7
	Сообщение от Slenon Я думаю о следующем - создаётся список нулевой длины и ему раз за разом присваивается значение функции находящейся в "цикле", после его окончания получившийся список, точнее его элементы, суммируются и таким образом мы обходим "проблему суммирования"... Во-первых, в ФП циклов тоже нет. Во-вторых, так имитировать аккумулятор невозможно, потому что аккумулятор в общем случае, не обязан накапливаться последовательно или синхронно, он может дергаться из совершенно различных мест программы 0