Вложенные отображения

Всем тем, кто осилил: Cвойство замыкания, на примере list и Иерархические структуры посвящается....
Мы разобрались как создавать абстрагированные последовательности, узнали приемы работы с ними. пришло время отчеркнуть линию и применить знания на примере!
Задача(для тех кто осилил еще и Простые числа вместе с Тест простоты =):
Пусть дано положительное целое число n; найти все такие упорядоченные пары различных целых чисел i и j, где 1 ≤ j < i ≤ n, что i+j является простым.
*-Нравится статья? Кликни по рекламе! :)
Например, если n равно 6, то искомые пары следующие:

Естественный способ организации этого вычисления состоит в том, чтобы породить последовательность всех упорядоченных пар положительных чисел, меньших n, отфильтровать ее, выбирая те пары, где сумма чисел простая, и затем для каждой пары (i, j), которая прошла через фильтр, сгенерировать тройку (i, j, i + j).
Вот способ породить последовательность пар: для каждого целого i ≤ n перечислить целые числа j < i, и для каждых таких i и j породить пару (i, j). В терминах операций над последовательностями, мы производим отображение последовательности - enumerateInterval(1, n). Для каждого i из этой последовательности мы производим отображение последовательности enumerateInterval(1, i-1). Для каждого j в этой последовательности мы порождаем пару (i, j). Это дает нам последовательность пар для каждого i. Скомбинировав последовательности для всех i (путем накопления через append), получаем необходимую нам последовательность пар.
Напишем функции отображения последовательностей:

def enumerateInterval(low, high):
    if low>high:
        return None
    return (low, enumerateInterval(low+1, high))

Накопление осуществляется посредством:

def accumulate(op, initial, sequence):
    if sequence is None:
        return initial
    return op(car(sequence), accumulate(op, initial, cdr(sequence)))

Комбинация из отображения и накопления через append в такого рода программах настолько обычна, что мы ее выразим как отдельную процедуру:

def append(l1, l2):
    if l1 is None:
        return l2
    return (car(l1), append(cdr(l1), l2))

def flatmap(proc, seq):
    return accumulate(append, None, map(proc, seq))

Теперь нужно отфильтровать эту последовательность пар, чтобы найти те из них, где сумма является простым числом. Предикат фильтра вызывается для каждой пары в последовательности; его аргументом является пара и он должен обращаться к элементам пары. Таким образом, предикат, который мы применяем к каждому элементу пары, таков:

def isPrimeSum(pair):
    return isPrime(car(pair)+cdr(pair), 2)

В качестве теста на простоту возьмем тест Ферма с основанием 2.

def isPrime(a,n):
    if a**(n-1)%n==1:
        return 1
    return 0

Функция фильтра выглядит следующим образом:

def filter(predicate, sequence):
    if sequence is None:
        return None
    if predicate(car(sequence)):
        return (car(sequence), filter(predicate, cdr(sequence)))
    return filter(predicate, cdr(sequence))

Наконец, нужно породить последовательность результатов, отобразив отфильтрованную последовательность пар при помощи следующей процедуры, которая создает тройку, состоящую из двух элементов пары и их суммы:

def makePairSum(pair):
    return (car(pair),(cdr(pair),(car(pair)+cdr(pair))))

Сочетание всех этих шагов дает нам процедуру целиком:

def primeSumPairs(n):
    return map(makePairSum, filter(isPrimeSum, flatmap(lambda i:map(lambda j: (i, j), enumerateInterval(1, i-1)), enumerateInterval(1, n))))

Используемая литература:

1. http://mitpress.mit.edu/sicp/