Использование ракетки для поиска только для одного «1»

Question

Я узнал, как использовать foldr и lambda, чтобы найти число 1 в списке. Но как использовать условие if или любой другой способ, чтобы проверить, если список содержит только один 1.

(define (exactlyone L) 
    (foldr (lambda (elem count) (if (equal? elem 1) (+ count 1) count)) 
     0 L) 

) 

Как можно использовать значение count в состоянии, если, если это возможно?

Answer 1

Вы не можете быть уверены в количестве 1 s, пока не пройдете весь список, поэтому обязательно foldr должен потреблять все предметы. После этого, это просто простой вопрос тестирования, если возвращаемое значение count было 1:

(define (exactlyOne L) 
    (= 1 
    (foldr (lambda (elem count) 
       (if (equal? elem 1) 
        (+ count 1) 
        count)) 
      0 
      L))) 

Конечно, самый простой способ будет использовать существующие процедуры (например, count), вместо того, чтобы изобретать колесо. Это будет работать в Ракетка:

(define (exactlyOne lst) 
    (= 1 
    (count (curry equal? 1) lst))) 

Например:

(exactlyOne '(1 2 3)) 
=> #t 

(exactlyOne '(1 2 3 1)) 
=> #f 

Answer 2

Проще всего было бы сделать свои собственные рекурсии:

(define (only-one predicate lst) 
    (let loop ((lst lst) (seen #f)) 
    (cond ((null? lst) seen) 
      ((not (predicate (car lst))) (loop (cdr lst) seen)) 
      ;; from here on we know predicate is true 
      (seen #f) ; at least two 
      (else (loop (cdr lst) #t))))) ; recurse with seen as #t 

Если вы хотите, чтобы решить эту проблему со складкой вы можете:

(define (only-one predicate lst) 
    (call/cc 
    (lambda (return) 
    (foldl (lambda (e seen) 
       (cond ((not (predicate e)) seen) ; keep seen (whatever it is) 
        (seen (return #f))   ; short circuit at second match 
        (else #t)))    ; change seen to #t 
      #f 
      lst)))) 

Это использует call/cc, чтобы получить процедуру выхода, если мы знаем результат до того, как все элементы обработаны. Это будет #f, если ни один или несколько совпадений, а #t - ровно один раз.

Оба произведения, как это:

(only-one (lambda (x) (equal? x 1)) '(0 1 2 3 4 5)) ; ==> #t 
(only-one (lambda (x) (equal? x 1)) '(2 3 4 5))  ; ==> #f 
(only-one (lambda (x) (equal? x 1)) '(0 1 2 1 3 4 5)) ; ==> #f 

Answer 3

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

псевдокод:

(foldl (let ([s 0]) 
     (lambda (accum item) 
      ;; if (equal? item 1) and s is not already 2 
      ;; increment s 
      ;; return (equal? s 1) 
     ) 
     #f list) 

Вы не можете решить эту проблему с помощью функции, которая не отражает какой-либо среды; но зачем это ограничивать? Функция - это код плюс лексическая среда, по определению.

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

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

1. Заметим, что результат должен быть Boolean: существует ровно один 1, правда или ложь?Таким образом, функция, которую мы используем как ядро ​​сложения, должна иметь булевский накопитель, так как аккумулятор - это то, что возвращается.

2. Аккумулятор складки инкапсулирует все состояние, на которое алгоритм функции ядра принимает решение. Если, например, функция использует лексическую область действия, которая содержит изменчивые переменные, которые будут обманывать.

3. Алгоритм требует не менее трех состояний в аккумуляторе. Аккумулятор должен быть в некоторых начальных S0, из которого он переходит к S1, когда 1 видно, из которого он переходит к S2 когда другой 1 виден. Затем этот аккумулятор следует интерпретировать за пределами складки как S0 и S2, обозначающий false, и S1 true.

4. Хотя мы могли бы теоретически изменить тип аккумулятора между посещенными элементами, у нас нет информации для этого; нам неизвестно, какой элемент последний. Если бы мы знали, что мы смотрим на последний элемент, мы можем потерять наш трехгосударственный накопитель до логического значения и вернуть его.

Поэтому вторая часть ответа Сильвестера использует продолжения: то алгоритм, вместо перехода к S2 могут выйти из складки непосредственно и производить ложный; тогда аккумулятор может быть булевым. (Более простой нелокальный механизм выхода будет достаточным вместо полномасштабных продолжений, таких как возврат из лексического блока).