用球拍在列表中搜索只有一個「1」

我已經找到了如何使用foldr和lambda找到列表中的1點的數量。但如何使用if狀況或任何其他的方法來驗證，如果列表中只有一個1用球拍在列表中搜索只有一個「1」

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

)

中如果有可能的，如果條件如何使用count價值？

來源

2016-10-04 anush95

在遍歷所有列表之前，您無法確定1的編號，因此必須使用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

來源

2016-10-04 15:35:30

最簡單的方法是做你自己的遞歸：

(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

來源

2016-10-04 16:50:31 Sylwester

這個問題可以，如果你允許摺疊的內核函數可以捕獲包含可變變量的詞法範圍內解決。然後，您可以保留累加器類型布爾值，並且具有足夠的狀態來進行計算。

僞代碼：

(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代表我們需要的一切。我們可以用一個布爾s，使得狀態是累加器PARAM的組合和s的信息。我們可以把一個布爾累加器和一個布爾s之間的狀態（讓他們一起組成一個代表所需的三種狀態的二位計數器）。

這是一個非正式的證據證明它不能只是一個布爾返回函數沒有變化無常的環境解決：

觀察，其結果必須是布爾：是，這正是一個1，對或錯？所以我們用作fold內核的函數必須有一個布爾累加器，因爲累加器就是返回的。
摺疊的累加器封裝了內核函數的算法作出決定的整個狀態。例如，如果函數使用包含可變變量的詞法作用域，那就是作弊。
該算法在累加器中需要至少三個狀態。累加器必須在一些初始S0，從它轉換到S1當1所看到的，從它當另一個1看出過渡到S2。這個累加器必須在摺疊之外解釋爲S0和S2表示錯誤，並且S1爲真。
儘管我們可以在理論上改變訪問項目之間的累加器類型，但我們沒有這方面的信息;我們不知道哪個元素是最後一個。如果我們知道我們正在查看最後一個元素，那麼可以將我們的三態累加器忽略爲一個布爾值並返回該值。

這就是爲什麼Sylwester的答案的第二部分使用延續：則算法，而不是過渡到S2可以逃脫出來直接折併產生虛假;累加器可以是布爾值。（一個非常簡單的非本地退出機制就足以代替全部的延續，比如從一個詞塊返回）。

來源

2016-10-04 19:02:50 Kaz

用球拍在列表中搜索只有一個「1」

回答

相關問題