迭代函數和分析結果在Haskell

Question

好了，回到我的previous question,我還在努力學習Haskell和解決從以下迭代尋找產業鏈最長的目前的問題：

chain n | n == 0  = error "What are you on about?" 
     | n == 1  = [1] 
     | rem n 2 == 0 = n : chain (n `div` 2) 
     | otherwise = n : chain (3 * n + 1) 

我有這一點排序，但我需要找到從1,000,000以下的起始數字中最長的鏈。那麼，如何讓每個起始數字達到1,000,000，然後打印鏈長最長的數字。 我可以用一個例子做：

Main> length (chain n) 

我想我需要的輸出作爲一個數組，然後使用maximum功能找到該值最大的鏈長，然後看看它是陣列中走多遠沿的答案。

這是尋找解決方案的好方法，還是有更好的方法（可能效率更高）？

Answer 1

你是對的maximum部分。要獲得列表（這就是Haskell的[] S是，數組是不同的結構），你需要使用map高階函數，就像這樣：

chainLength n = length (chain n) 

lengths = map chainLength [1..1000000] 

從本質上講，map需要作爲自變量的函數和一個列表。它將函數應用於列表中的每個元素並返回結果列表。

既然你也將需要其鏈有長度的數量，可能要改變chainLength函數返回的數量爲好，像這樣：

chainLength n = (n, length (chain n)) 

這樣，你將擁有對數組，每個數字和它的鏈長。

現在你需要得到最大的第二個組件對。這就是maximumBy函數的作用。它的工作原理與maximum類似，但是它將函數作爲參數來選擇如何比較值。在這種情況下，這一對的第二個組成部分。該比較函數需要兩個數字並返回Ordering類型的值。這種類型只有三種可能的值：分別爲LT，EQ,GT，分別小於，等於和大於。

所以，我們需要給兩對功能告訴我們第二個組件是如何互相比較：

compareSnd (_, y1) (_, y2) = compare y1 y2 
-- Or, if you import Data.Function, you can write it like this (thanks alexey_r): 
compareSnd = compare `on` snd     -- reads nicely 

我使用了默認compare功能比較數字（當然，not just numbers）。

現在，我們只需要使用此功能，以獲得最大：

longestChain = maximumBy compareSnd lengths 

，讓你一對數的最長鏈和相應的長度。歡迎隨時申請fst和snd。

請注意，這可以更簡潔地使用zip和組合，但由於您將問題標記爲新手，我認爲最好這樣分解。

Answer 2

喜歡的東西

fst $ maximumBy (length . snd) $ zip [1..1000000] $ map chain [1..1000000] 

（未經測試）

即不工作了多遠沿着產業鏈最長爲最長鏈的名單，但周圍的種子值隨身攜帶的鏈，而不是。

Answer 3

SPOILER（100下解決該問題爲正整數）：

module Test where 
import Data.List -- this contains maximumBy 

chain n 
     | n == 0  = error "What are you on about?" 
     | n == 1  = [1] 
     | rem n 2 == 0 = n : chain (n `div` 2) 
     | otherwise = n : chain (3 * n + 1) 

chains = map (\x -> (x,chain x)) [1..100] 

cmpSnd (a,b) (c,d) 
     | length b > length d  = GT 
     | length b == length d = EQ 
     | otherwise    = LT 

solve = (fst . maximumBy cmpSnd) chains 

鏈條功能使用地圖的。它適用於一個值的列表中的每個元素的功能，所以

map succ [1,2] 

相同

[succ 1,succ 2] 

的cmpSnd功能，可能在Hierarchical Libraries深某處有一個比較功能，但我無法找到它，所以我創建了它。 GT的意思是「第一個價值大於第二個價值」，其餘都是微不足道的。

解決方案採用列表的最大值（通過利用我們之前定義的比較函數）。這將是一對整數和一個列表。它只會返回整數（因爲fst）。

評論：你的鏈函數不是尾遞歸的。這意味着大型鏈將不可避免地導致堆棧溢出。您應該添加一個明確的累加器變量並進行尾遞歸。

Answer 4

幾年前我學習了Haskell，所以我不記得那件事。另一方面，我測試了這個代碼，它的工作原理。您將獲得最大鏈和生成它的數字。但正如之前所說的那樣，它會因大價值而溢出。

chain :: Int -> [Int] 
chain n 
    | n == 0 = [] 
    | n == 1 = [1] 
    | rem n 2 == 0 = n : chain (n `div` 2) 
    | otherwise = n : chain (3 * n + 1) 

length_chain :: Int -> Int 
length_chain n = length (chain n) 

max_pos :: (Int,Int) -> Int -> [Int] -> (Int,Int) 
max_pos (m,p) _ [] = (m,p) 
max_pos (m,p) a (x:xs) 
    | x > m = max_pos (x,a) (a+1) xs 
    | otherwise = max_pos (m,p) (a+1) xs 

指令將

Main> max_pos (0,0) 1 (map length_chain [1..10000]) 
(262,6171)