我知道不可能對無限串列進行排序，但我正在嘗試撰寫n數倍數的無限遞增串列的定義。
我已經有了這個功能
multiples :: Integer -> [Integer]
multiples n = map (*n) [1..]
回傳n倍數的無限串列。但是現在我想構建一個函式，該函式給出一個Integers回傳串列中所有數字的倍數的遞增無限串列。所以multiplesList :: [Integer] -> [Integer]給定輸入的函式[3,5]應該是 yield [3,5,6,9,10,12,15,18,20,....]。
我是 Haskell 的新手，我正在為此苦苦掙扎。我想我應該使用foldrormap因為我必須應用multiples到輸入中的所有數字，但我不知道如何。我無法將所有串列混合為一個。
如果有人可以幫助我，我將不勝感激。
謝謝！
uj5u.com熱心網友回復：
你走在正確的道路上。此處的評論后是您可以完成的模板。
multiples :: Integer -> [Integer]
multiples n = map (*n) [1..]
-- This is plain old gold recursion.
mergeSortedList :: [Integer] -> [Integer] -> [Integer]
mergeSortedList [] xs = undefined
mergeSortedList xs [] = undefined
mergeSortedList (x:xs) (y:ys)
| x < y = x:mergeSortedList xs (y:ys) -- Just a hint ;)
| x == y = undefined
| x > y = undefined
multiplesList :: [Integer] -> [Integer]
multiplesList ms = undefined -- Hint: foldX mergeSortedList initial xs
-- Which are initial and xs?
-- should you foldr or foldl?
uj5u.com熱心網友回復：
我們可以輕松地在位置上將兩個無限串列編織在一起，在每一步從每個串列中取出一個元素，
weave (x:xs) ys = x : weave ys xs
或者我們每次都可以使用更長的前綴，
-- warning: expository code only
weaveN n xs ys = take n xs weaveN n ys (drop n xs)
但是假設兩個串列不僅是無限的而且是嚴格遞增的（即串列中沒有重復項），我們可以通過相反串列的頭部值來引導前綴的取用：
umerge :: Ord a => [a] -> [a] -> [a]
-- warning: only works with infinite lists
umerge xs (y:ys) = a [y | head b > y ] umerge ys b
where
(a,b) = span (< y) xs
因此，這是唯一合并操作的可能編碼（“唯一”的意思是，其輸出中不會有任何重復項）。
測驗，它似乎按預期作業：
> take 20 $ umerge [3,6..] [5,10..]
[3,5,6,9,10,12,15,18,20,21,24,25,27,30,33,35,36,39,40,42]
> [3,6..42] [5,10..42] & sort & nub
[3,5,6,9,10,12,15,18,20,21,24,25,27,30,33,35,36,39,40,42]
> [ p | let { ms :: [Integer] ; ms = takeWhile (< 25^2) $
foldl1 umerge [[p*p,p*p p..] | p <- [2..25]] },
p <- [2..545], not $ elem p ms ]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,
97,101,...........,499,503,509,521,523,541]
> length it
100
并且通過巧妙的小調整（由于在Melissa O'Neill的 JFP 文章中看到的 Richard Bird ），它甚至可以用于折疊無限的升序串列，前提是它按其頭部元素的升序排序，所以第一個引數的頭部保證是輸出中的第一個，因此可以在沒有測驗的情況下生成：
umerge1 :: Ord a => [a] -> [a] -> [a]
-- warning: only works with infinite lists
-- assumes x < y
umerge1 (x:xs) ~(y:ys) = x : a [y | head b > y ] umerge ys b
where
(a,b) = span (< y) xs
現在
> take 100 [ p | let { ms :: [Integer] ;
ms = foldr1 umerge1 [[p*p,p*p p..] | p <- [2..]] },
p <- [2..], not $ elem p $ takeWhile (<= p) ms ]
[2,3,5,7,11,13, ...... 523,541]
相同的計算無限期地作業。
to the literalists in the audience: yes, calling elem here is Very Bad Thing. The OP hopefully should have recognized this on their own, (*) but unfortunately I felt compelled to make this statement, thus inadvertently revealing this to them, depriving them of their would-be well-earned a-ha moment, unfortunately.
Also, umerge1's definition can be radically simplified. Again, this is left to the OP to discover on their own. (which would, again, be much better for them if I wasn't compelled to make this remark revealing it to them --- finding something on your own is that much more powerful and fulfilling)
(*) and search for ways to replace it with something more efficient, on their own. No, this code is not presented as The Best Solution to Their Problem.
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/316798.html
上一篇：tomcatjvm引數丟失