Функциональное программирование - реализация сканирования (сумма префикса) с использованием Fold - PullRequest
Новая
       12

Функциональное программирование - реализация сканирования (сумма префикса) с использованием Fold

4 голосов
/ 11 февраля 2010

Я учил себя функциональному программированию, и в настоящее время я пишу различные функции более высокого порядка, используя сгибы. Я застрял реализации сканирования (также известный как префикс суммы). Моя реализация карты с использованием сгиба выглядит так: 

(define (map op sequence)
  (fold-right (lambda (x l) (cons (op x) l)) nil sequence))

И мой снимок при сканировании выглядит так: 

(define (scan sequence)
  (fold-left (lambda (x y) (append x (list (+ y (car (reverse x)))))) (list 0) sequence))

Мое наблюдение состоит в том, что "x" является результирующим массивом до сих пор, а "y" является следующим элементом во входящем списке. Это производит: 

(scan (list 1 4 8 3 7 9)) -> (0 1 5 13 16 23 32)

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

У кого-нибудь есть более элегантное решение для сканирования?

Кстати, моя реализация сгибания влево и сгибания вправо: 

(define (fold-left op initial sequence)
 (define (iter result rest)
  (if (null? rest)
   result
   (iter (op result (car rest)) (cdr rest))))
 (iter initial sequence))

(define (fold-right op initial sequence)
 (if (null? sequence)
  initial
  (op (car sequence) (fold-right op initial (cdr sequence)))))

Ответы [ 3 ]

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

Сканирование Imho очень хорошо выражено в терминах fold.

Пример Haskell: 

scan func list = reverse $ foldl (\l e -> (func e (head l)) : l) [head list] (tail list)

Должен перевести что-то вроде этого 

(define scan
  (lambda (func seq)
    (reverse 
      (fold-left 
       (lambda (l e) (cons (func e (car l)) l))
       (list (car seq))
       (cdr seq)))))
3 голосов
/ 11 февраля 2010

Я бы не стал этого делать. fold может быть реализовано в терминах scan (последний элемент отсканированного списка). Но scan и fold фактически являются ортогональными операциями. Если вы прочитали документы CUDA, вы заметите, что сканирование состоит из двух этапов: первый дает результат сгиба как побочный продукт. Второй этап используется только для сканирования (конечно, это учитывается только для параллельных реализаций; последовательная реализация fold более эффективна, если вообще не полагается на scan).

1 голос
/ 09 апреля 2010

imho Дарио обманывал, используя реверс, поскольку упражнение было выражено в терминах сгиба, а не сгиба назад. Это, конечно, ужасный способ выразить сканирование, но это забавное упражнение - втиснуть квадратный колышек в круглое отверстие.

Вот оно в хаскеле, я не знаю, шепот 

let scan f list = foldl (\ xs next -> xs++[f (last xs) next]) [0] list
scan (+) [1, 4, 8, 3, 7, 9]
[0,1,5,13,16,23,32]

Конечно, используя тот же трюк, что и Дарио, можно избавиться от этой ведущей 0: 

let scan f list = foldl (\ xs next -> xs++[f (last xs) next]) [head list] (tail list)
scan (+) [1, 4, 8, 3, 7, 9]
[1,5,13,16,23,32]
...