Заблокирован
1

Отличие правой и левой свертки

14.08.2016, 16:03. Показов 1633. Ответов 3
Метки нет (Все метки)

Правую и левую свертку можно реализовать так:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#!/usr/bin/racket
#lang scheme
 
(define (fold-right op initial sequence)
        (if (null? sequence)
                initial
                (op (car sequence) (fold-right op initial (cdr sequence)))))
 
(define (fold-left op initial sequence)
        (define (iter result rest)
                (if (null? rest)
                        result
                        (iter (op result (car rest))
                              (cdr rest))))
        (iter initial sequence))
 
 
(display (fold-left * 1 (list 1 2 3 4 5)))
(newline)
 
(display (fold-right * 1 (list 1 2 3 4 5)))
(newline)
В книге написано, что эти свертки называются правой и левой потому, что в них разное направление комбинации элементов моноида. Я не совсем понимаю, как определяется направление в левой свертке, ведь она представляет собой правую свертку, в которой сделали хвостовую рекурсию.

Алгоритм foldr: вся последовательность (op A (op B (op C ... (op Z 1)))) сначала разворачивается, а потом происходит редукция с хвоста. Здесь 1 - нейтральный элемент некоторой алгебраической структуры.

В алгоритме foldl сразу же начинается редукция с хвоста. Это можно записать как (op (op (op 1 A) B) C ... ))), где вычисление начинается изнутри.

Направление свертки видно в foldr, но в foldl я его пока не заметил. Зато заметна роль ассоциативности операции.
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.08.2016, 16:03
Ответы с готовыми решениями:

При нажатии левой клавиши "мыши" отразить курсор в левой половине экрана, а при нажатии правой - в правой
При нажатии левой клавиши "мыши" отразить курсор в левой половине экрана, а при нажатии правой - в...

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

Рисунки с левой и с-правой сторону
Подскажите как сделать рисунок с левой стороны и с правой? я сделал но у меня криво отображается...

ПравилА левой и правой руки
Помогите пожалуйста с правилами левой и правой руки со всеми тонкостями)) Постоянно путаю все....

3
Модератор
Эксперт функциональных языков программированияЭксперт Python
29594 / 16157 / 3228
Регистрация: 12.02.2012
Сообщений: 26,731
Записей в блоге: 5
14.08.2016, 16:37 2
Я очевидным образом переписал эти функции в Common Lisp. Вот что у меня получилось:

1) Правая свертка:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
(defun fold-right (op initial sequence)
  (if (null sequence) 
      initial
      (funcall op (car sequence) (fold-right op initial (cdr sequence)))))
 
==> fold-right
 
(trace fold-right)
 
==> fold-right
 
(fold-right '* 1 (list 1 2 3 4 5))
 
  Вход в функцию fold-right Аргументы: * 1 (1 2 3 4 5)
    Вход в функцию fold-right Аргументы: * 1 (2 3 4 5)
      Вход в функцию fold-right Аргументы: * 1 (3 4 5)
        Вход в функцию fold-right Аргументы: * 1 (4 5)
          Вход в функцию fold-right Аргументы: * 1 (5)
            Вход в функцию fold-right Аргументы: * 1 NIL
            Возврат из функции fold-right Результат: 1
          Возврат из функции fold-right Результат: 5
        Возврат из функции fold-right Результат: 20
      Возврат из функции fold-right Результат: 60
    Возврат из функции fold-right Результат: 120
  Возврат из функции fold-right Результат: 120
 
==> 120
2) Левая свертка:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(defun fold-left (op initial sequence)
 (labels ((ite (result rest)
     (print result)(prints " ")(printline rest) ;; отладочная печать
            (if (null rest)
                result
                (ite (funcall op result (car rest))(cdr rest)))))
        (ite initial sequence)))
 
==> fold-left
 
(fold-left '* 1 (list 1 2 3 4 5))
 
1 (1 2 3 4 5)
1 (2 3 4 5)
2 (3 4 5)
6 (4 5)
24 (5)
120 NIL
 
==> 120
Хорошо видно, что правая свертка умножает элементы от последнего к первому, а левая - от первого к последнему.
0
Заблокирован
14.08.2016, 17:13  [ТС] 3
а левая - от первого к последнему
Ой, что-то я, похоже, написал здесь свои прошлые мысли на момент разбора этих функций. Потом я понял нечто, но забыл.
0
4492 / 2112 / 266
Регистрация: 01.03.2013
Сообщений: 5,600
Записей в блоге: 22
14.08.2016, 18:29 4
1. Свертка не обязательно по моноиду, у бинарной операции может не существовать нейтрального элемента
2. Языки бывают строгие и ленивые. В ленивых левая свертка без принудительной редукции промежуточных термов неоптимально разворачивает санки в памяти, вдобавок не позволяет сворачивать бесконечные структуры (списки), в отличие от правой свертки. В строгих языках левая сверка хвосторекурсивна в отличие от правой, поэтому не забивает стек если есть ТСО.

ЗЫ А наивное отличие уже сказали - разный порядок обработки элементов. У меня, например, реверс списка в библиотеке реализован как левая свертка по консу от нила
3
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.08.2016, 18:29

Код левой и правой кнопки мышки
Нужны коды кнопок мышки, в Keys не нашёл. Я использую следующий код для захвата кнопок: protected...

Отличие левой части математического ряда
3 ряда: сумма от n=1 до бесконечности... Un=... и Vn=... где ...выражение. Un и Vn или знак суммы...

Однозначная грамматика без правой и левой рекурсии
Всем привет! Сижу, зубрю системное программирование и наткнулся на такой вопрос: верно ли...

Ввод текста в TEdit с правой стороны, а не с левой
Можнали сделать чтобы текст в редакторе Edit вводился не с левой части а с правой.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.