Треугольник Паскаля в Haskell


Приведенный ниже код создает список Паскаль коэффициентов. е.г pascalList 3 выходы [[1], [1,1], [1,2,1], [1,3,3,1] Мы можем написать ниже образец в более идиоматические способ

pascalList 0 = [[1]]
pascalList 1 = [[1], [1, 1]]
pascalList n = let pList = pascalList (n-1)
               in pList ++ [([1] ++ pascalCoeff (last pList) ++ [1])]
  where pascalCoeff (x:y:ys) = (x+y) : pascalCoeff (y:ys)
        pascalCoeff (x:[]) = []

Следующий печатает код, приведенный выше список

listtoString :: [Int] -> String
listtoString [] = []
listtoString [x] = show x
listtoString (x:xs) = show x ++ " " ++ listtoString xs

pascalTriangle :: Int -> IO ()
pascalTriangle n = mapM_ putStrLn (((justify n) . map listtoString) (pascalList n))

justify :: Int -> [String] -> [String]
justify n (x:xs) = (concat (replicate n " ") ++ x) : justify (n-1) xs
justify _ [] = []

Образец выходных данных pascalTriangle 4 будет

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1


272
3
задан 3 апреля 2018 в 01:04 Источник Поделиться
Комментарии
2 ответа

Я не знаю, если это более идиоматические, но с тех пор, как я видел бесконечный список работ для чисел Фибоначчи, я был в нее влюблен, так что здесь ничего не происходит.

pascalTriangle :: [[Integer]]
pascalTriangle = [1] : map newRow pascalTriangle
where newRow y = 1 : zipWith (+) y (tail y) ++ [1]

Чтобы понять это, может быть, сначала вы должны посмотреть на простые примеры, например, бесконечный список нулей,

zeros = 0 : zeros

или список натуральных чисел,

nats = 0 : map (+1) nats

или мое любимое, список чисел Фибоначчи,

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)


Это, как говорится...

Линии

pascalList 1 = [[1], [1, 1]]

является ненужным, потому что вы уже указали pascalList 0. Линии

[([1] ++ pascalCoeff (last pList) ++ [1])]

эквивалентно

[[1] ++ pascalCoeff (last pList) ++ [1]]

что эквивалентно

[ 1 : pascalCoeff (last pList) ++ [1]]

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

pascalCoeff (x:y:ys) = (x+y) : pascalCoeff (y:ys)
pascalCoeff (x:[]) = []

Я бы сказал, что эта функция принимает список например [1,2,3,4] и делает следующее:

  [1, 2, 3]
[2, 3, 4]
+ ---------
[3, 5, 7]

так он принимает tail (все, кроме первого элемента) из списка, и init (все, кроме последнего элемента) из списка, и складывает их элемент-мудрый.

Есть встроенные функции tailи init что даст вам эти детали из списка, и, к счастью, функция

zipWith (+)

не добавляя части, так что вы можете просто сказать

pascalCoeff y = zipWith (+) (init y) (tail y)

что, из-за способа zipWith работает, как и

pascalCoeff y = zipWith (+) y (tail y)


Аналогично,

listtoString [] = []
listtoString [x] = show x
listtoString (x:xs) = show x ++ " " ++ listtoString xs

может просто быть

listToString = unwords . map show


И

justify :: Int -> [String] -> [String]
justify n (x:xs) = (concat (replicate n " ") ++ x) : justify (n-1) xs
justify _ [] = []

может быть

justify n ss = zipWith (++) padding ss
where padding = [ replicate k ' ' | k <- [n, n-1 .. 1]]

или, что эквивалентно, после Эрп-сокращение

justify n = zipWith (++) padding
where padding = [ replicate k ' ' | k <- [n, n-1 .. 1]]


Из-за того, что списки связанные списки, добавление в список стоит дорого, в то время как добавляя к нему дешевые. Итак, если вы все-таки решили построить список поэлементно, то я бы сказал, что вы должны добавлять новые элементы и, возможно, после того, как список будет построен, использовать reverse.

По той же логике, head дешево, last дорого.

Вот возможная реализация, которая использует то, что я только что сказал.

pascalList = reverse . pascalList'
pascalList' 0 = [[1]]
pascalList' n = new : old
where new = 1 : pascalCoeff (head old) ++ [1]
old = pascalList' (n-1)


На мой взгляд это хорошая идея


  • отдельный чистых и нечистых код,

  • сохранить ваш код как модульная, как это возможно,

  • писать подписей типа,

  • использовать линтер как hlint,

  • использовать функции из стандартной библиотеки, а не писать явной рекурсии.

Имея это в виду, вот как я напишу печатной части.

listToString :: (Show a) => [a] -> String
listToString = unwords . map show

leftPadStrings :: [String] -> [String]
leftPadStrings ss = map leftPad ss
where maxlen = maximum $ map length ss
leftPad s = replicate (div (maxlen - length s) 2) ' ' ++ s

paddedPascalTriangle :: Int -> [String]
paddedPascalTriangle n = leftPadStrings
. map listToString
. take n
$ pascalTriangle

printPascalTriangle :: Int -> IO ()
printPascalTriangle = mapM_ putStrLn . paddedPascalTriangle

Выполнение этого, вы должны сделать что-то вроде следующего:

*Main> printPascalTriangle 10
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

6
ответ дан 3 апреля 2018 в 04:04 Источник Поделиться

Третий случай включает в себя второй. Все возможные списки результатов префиксы такой же бесконечный список - давайте определимся, что вместо. iterate захватывает этот шаблон. Сочетание zipWith и tail захватывает pascalCoeff.

pascalList :: [[Int]]
pascalList = flip iterate [1] $ \pList -> 1 : zipWith (+) pList (tail pList) ++ [1]

4
ответ дан 3 апреля 2018 в 08:04 Источник Поделиться