DrRacket結合列表

我希望有人能指導我在正確的方向：我找2生產項目的所有可能的組合在兩個列表：
例子：
鑑於名單「（符號1 symbol2）和」（ 1 2），我期待產生：
（名單（名單 '符號1 1）（名單' 符號1 2）（名單「symbol2 1）（名單symbol2 2））DrRacket結合列表

我的代碼到目前爲止是：

(define (combiner list1 list2) 
    (list 
     (foldr (lambda (a b) (foldr (lambda (c d) (list a c)) empty list1)) empty list2) 
     (foldr (lambda (a b) (foldr (lambda (c d) (list b d)) empty list1)) empty list2)))

這顯然不起作用，而且我也嘗試過其他幾種方法。我無法處理兩個列表上的隱式遞歸 - 任何想法？

來源

2011-11-19 David

我想到另一種解決問題的可能方法。這裏有一個提示：

(define (combiner list1 list2) 
    (define (combine l1 l2) 
    (cond ((empty? l1) empty) 
      ((empty? l2) XXX) 
      (else (cons YYY 
         ZZZ)))) 
    (combine list1 list2))

在上面的代碼，你必須回答弄清楚三個問題：

XXX你如何推進遞歸當你完成迭代在第二個列表中，但第一個列表仍然有元素，並且您還想在第一個列表中推進一個元素？
YYY如何將第一個列表中的元素與第二個列表中的元素結合起來？
ZZZ當兩個列表中仍有元素時，如何提前遞歸，但此時您只對第二個列表感興趣？

最後一個提示：請注意，在某些時候，你需要「重啓」第二個列表，對於這一點，你可以參考原list2，這沒有改變。

我希望這可以幫助你，我不想給你一個直接的答案（但） - 我希望你自己找出解決方案。

來源

2011-11-19 02:16:34

感謝所有提交幫助的人！奧斯卡，我同意這是一個很好的解決方案，但我需要找到一個使用lambda和foldr的解決方案。幸運的是，我設法解決了這個問題......保留一個在另一個之內！非常感謝！ – David

你在這裏看到的是關於如何設計程序的兩個複雜參數section 17的遞歸。如果你想要另一個提示，我會告訴你這三個案例中的哪一個。

來源

2011-11-19 01:14:30

嗨，約翰。感謝您的回覆。我看了一下，我相信我正在處理案例3.我已經設計了一個遞歸函數來解決這類問題，但是我沒有看到如何使用lambda和foldr來做到這一點。我看到foldr本質上是如何處理遞歸的，但我只是沒有看到如何讓它在同一時間在兩個列表上工作。 – David

我想我需要睡一會兒！ – David

我已經想通了如何讓（名單（名單「符號1 1）（名單」符號1 2）） – David

看來，這裏可能會增加混淆的一點是自由使用list。我將開始用類型的Haskell符號來解決你的問題。 ::表示「有類型」，[Foo]表示「Foo列表」。

list1 :: [Symbol] 
list2 :: [Number] 
type Pair = (Symbol, Number) 
(combiner list1 list2) :: [Pair]

現在它看起來像你想用一個foldr在列表2來解決這個問題。

foldr :: (a -> b -> b) -> b -> [a] -> b

foldr相似，需要一個step :: a -> b -> b和start :: b。由於我們希望最終結果爲[Pair]，這意味着b = [Pair]。那麼start可能是空的列表。由於list2填充[a]插槽，這意味着a = Number。因此，對於我們的問題，step :: Number -> [Pair] -> [Pair]

combiner :: [Symbol] -> [Number] -> [Pair] 
combiner list1 list2 = foldr step start list2 
    where step :: Number -> [Pair] -> [Pair] 
     step a b = undefined 
     start = []

到目前爲止，這是一樣的，你寫的，但我還沒有定義step尚foldr。那麼step功能是什麼？從該類型中，我們知道它必須採用Number和[Pair]並生成[Pair]。但是這些輸入是什麼意思？那麼Number輸入將是list2的一些元素。 [Pair]輸入將是「到目前爲止的結果」。 所以我們想要拿我們的Number，做爲它創建Pair s，然後將它們拍到目前爲止的結果。這是我的代碼開始與你不同的地方。

step a b = append (doSomething a) b 
doSomething :: Number -> [Pair] 
doSomething a = undefined

既然你，用球拍，可能會定義doSomething作爲一個匿名函數，這意味着list1是在範圍內。（因爲它位於Haskell函數的where子句中，所以它在範圍內）。您可能會使用該列表來生成組合。

doSomething a = ... a ... list1 ...

實施doSomething就留給讀者做練習，如翻譯回球拍。請注意，我在此定義的Haskell函數的類型簽名combiner可以推廣到[a] -> [b] -> [(a,b)]。

來源

2011-11-19 02:48:31

DrRacket結合列表

回答

相關問題