Треугольник Паскаля в Хаскеле
Я новичок в Haskell, и мне действительно нужна помощь!
Я должен написать программу, которая включает в себя рекурсивную функцию для создания списка биномиальных коэффициентов для степени n=12, используя технику треугольника Паскаля.
У меня есть некоторые идеи в голове, но, поскольку я только начинаю, я понятия не имею, как реализовать это в haskell?!
Может ли кто-нибудь помочь мне?
first row: (a+b)^0 = 1
second row: (a+b)^1 = 1a+1b
third row: (a+b)^2 = 1a^2+2ab+1b^2
и так далее... это моя главная идея. Но я даже не могу попробовать это, потому что я понятия не имею, как поместить это в Haskell.. получая ошибки все время
5 ответов
Начнем с присвоения индекса каждому элементу в треугольнике:
| 0 1 2 3 4 5 6 -+-------------------------- 0 | 1 1 | 1 1 2 | 1 2 1 3 | 1 3 3 1 4 | 1 4 6 4 1 5 | 1 5 10 10 5 1 6 | 1 6 15 20 15 6 1
Здесь я просто положил треугольник на его сторону, чтобы мы могли их нумеровать. Так что здесь я бы сказал, что элемент в (6, 4) является 15, в то время как (4, 6) не существует Теперь сосредоточиться на написании функции
pascal :: Integer -> Integer -> Integer
pascal x y = ???
Такой, что вы можете сгенерировать эту версию треугольника. Вы можете начать писать
pascal x y
| x == 0 = 1
| x == y = 1
| x < y = error "Not a valid coordinate for Pascal's triangle."
| otherwise = pascal ? ? + pascal ? ?
Обратите внимание, что здесь, вместо того, чтобы выяснить, какие элементы должны быть добавлены по диагонали, вы можете сделать это через прямоугольные координаты. Здесь вы заметите, что y это какой ряд в треугольнике вы находитесь и x это позиция элемента в этой строке. Все, что вам нужно сделать, это выяснить, что идет вместо ?s.
После того, как вы это заработаете, у меня есть однострочник для этого треугольника, который более эффективен и может генерировать весь треугольник одновременно, при этом используя рекурсию:
import Data.List (scanl1)
pascals :: [[Integer]]
pascals = repeat 1 : map (scanl1 (+)) pascals
Не пытайтесь передать это решение своему профессору, это не то, что они ищут, и было бы совершенно очевидно, что кто-то дал вам это решение, если вы работали на Haskell всего неделю. Тем не менее, это действительно показывает, насколько мощным может быть Haskell для такого рода проблем. Я бы показал, как индексировать pascals чтобы получить данный (n, k) значение, но это также даст вам слишком много советов для решения наивной рекурсии.
Поскольку возникла некоторая путаница, причина, по которой я дал это решение, заключается в том, чтобы провести параллель между ним и часто показанной ленивой реализацией для последовательности Фибоначчи:
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
По сравнению с
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
Это определение генерирует бесконечный список всех чисел Фибоначчи и делает это достаточно эффективно (с точки зрения ЦП, ОЗУ - это отдельная история). Он кодирует в своих первых 2 элементах базовый случай, а затем рекурсивное выражение, которое может вычислить остальные. Для Фибоначчи вам нужно 2 значения, чтобы начать, но для треугольника Паскаля вам нужно только одно значение, это значение оказывается бесконечным списком. В столбцах сетки, которую я разместил выше, легко увидеть шаблон, scanl1 (+) Функция просто использует преимущества этого шаблона и позволяет нам очень легко сгенерировать его, но это генерирует диагонали треугольника, а не строки. Чтобы получить строки, вы можете проиндексировать этот список, или вы можете сделать некоторые хитрые трюки с take, dropи другие подобные функции, но это упражнение для другого дня.
Начните с самого треугольника:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...
Вы должны заметить, что для записи следующей строки вы должны применить это правило: суммируйте соседние элементы предыдущих строк, используя 0 для одиноких краевых элементов. Визуально:
0 1 0
\+/ \+/
0 1 1 0
\+/ \+/ \+/
0 1 2 1 0
\+/ \+/ \+/ \+/
1 3 3 1
...
Оперативно это выглядит так:
For row 0:
[1] (it's a given; i.e. base case)
For row 1:
[0, 1] <- row 0 with a zero prepended ([0] ++ row 0)
+ +
[1, 0] <- row 0 with a zero appended (row 0 ++ [0])
= =
[1, 1] <- element-wise addition
For row 2:
[0, 1, 1]
+ + +
[1, 1, 0]
= = =
[1, 2, 1]
Generally, for row N:
element-wise addition of:
[0] ++ row(N-1)
row(N-1) ++ [0]
Помните, что поэлементное добавление списков в Haskell zipWith (+),
Таким образом, мы приходим к следующему определению Хаскеля:
pascal 0 = [1]
pascal n = zipWith (+) ([0] ++ pascal (n-1)) (pascal (n-1) ++ [0])
Или в моде, похожем на знаменитые "ленивые выдумки":
pascals = [1] : map (\xs -> zipWith (+) ([0] ++ xs) (xs ++ [0])) pascals
Другое возможное решение (более подходящее для начинающих, на мой взгляд):
pascal :: Integer -> [Integer]
pascal 0 = [1]
pascal 1 = [1, 1]
pascal n = let p = pascal (n - 1)
in [1] ++ pascalStep p ++ [1]
pascalStep :: [Integer] -> [Integer]
pascalStep [] = []
pascalStep [_] = []
pascalStep (x:y:xs) = x + y : pascalStep (y : xs)
С помощью let чтобы избежать большего использования пространства.pascal вызывает рекурсивно, чтобы найти все предыдущие строки, используя их для получения следующей строки, пока не доберется до нужной строки.
Выход:
*Main> pascal 3
[1,3,3,1]
*Main> pascal 4
[1,4,6,4,1]
*Main> pascal 5
[1,5,10,10,5,1]
Начните с базового варианта.
pascal 0 0 = 1
Тогда обработайте крайние случаи
pascal n 0 = 1
pascal n r | n == r = 1
Теперь разверните с рекурсивным шагом
pascal n r = pascal (n - 1) (r - 1) + pascal (n - 1) r
Если вы хотите список для конкретной строки, напишите обертку
binom n = map (pascal n) [0..n]
Выяснить типы не должно быть сложно
pascal :: Integral a => a -> a -> a
binom :: Integral a => a -> [a]
Я сижу на своем телефоне, так что извините за ошибки, но вы можете использовать ленивую оценку Haskell действительно классным способом здесь.
pascals :: [[Int]]
pascals = [1]:map (\r -> zipWith (+) (0:r) (r++[0])) pascals
Который вы могли бы сделать без точки с помощью вилки, но это довольно эзотерично.
pascals :: [[Int]]
pascals = [1]:map ((zipWith (+) -<) (0:) (++[0])) pascals
Но лично мне очень нравится этот код, и я думаю, что его стоит читать.
pascals :: [[Int]]
pascals = [1]:map next pascals
where next = (zipWith (+) -<) (0:) (++[0])
Но подобные комбинаторы могут немного сбивать с толку, как бы мне ни нравилось бесточечное программирование.