треугольник паскаль в вложенных списках на haskell - PullRequest
Новая
       9

треугольник паскаль в вложенных списках на haskell

0 голосов
/ 03 мая 2018

я пытаюсь получить k-ую строку в каждом списке в списке паскалей. Например, Паскаль 4 получит 4-й элемент в каждом ряду. Таким образом, он вернул бы 1,4,10,20 ... и т. Д. Я понимаю, как создать бесконечный список паскалей, который выводит ниже, но я не уверен, как получить n-й элемент в каждом вложенном списке. какие-либо предложения? я думал об использовании карты, но я не обязательно отображал здесь функцию, которая немного сбивает меня с толку. благодарю вас. 

// im trying to get pascal k to return the nth element of every row in the triangle
pascal n = map(\n -> ??) take n pascal 
pascal_infite = [1] : map (\l -> zipWith (+) (l ++ [0]) (0:l)) pascal_infinite

Ответы [ 2 ]

0 голосов
/ 03 мая 2018

В основном это функция iterate :: (a -> a) -> a -> [a], в которой у вас есть состояние, и каждый раз, когда вы обновляете состояние и, таким образом, создаете список элементов.

Как итеративная функция, мы в основном хотим выполнить zipWith (+) с предыдущим списком xs и (0:xs), но там, где мы продолжаем итерацию, пока оба списка не будут исчерпаны. Мы можем реализовать zipWithLongest для этого: 

zipWithLongest :: a -> b -> (a -> b -> c) -> [a] -> [b] -> [c]
zipWithLongest x0 y0 f = go
    where go (x:xs) (y:ys) = f x y : go xs ys
          go [] t = map (f x0) t
          go t [] = map (flip f y0) t

Итак, теперь мы можем составить список, используя: 

import Control.Monad(ap)

pascalTriangle :: Num n => [[n]]
pascalTriangle = iterate (ap (zipWithLongest 0 0 (+)) (0:)) [1]

Мы можем проиндексировать список, используя (!!) :: [a] -> Int -> a. Однако обратите внимание, что это обычно немного против паттерна по двум причинам:

  1. поиск занимает O (k) время с k значением индекса, который мы хотим получить; и
  2. это частичная функция в том смысле, что индекс может быть вне диапазона (здесь отрицательный индекс, а для конечных списков слишком большой индекс).

Мы знаем, что каждая следующая строка треугольника Паскаля содержит на один элемент больше, чем предыдущая строка. Таким образом, k -я строка содержит k элементов. Если мы хотим получить k -й элемент каждого подсписка, то сначала следует игнорировать все списки, в которых нет k -го элемента. Поэтому мы используем drop k для удаления первых k -элементов списка, а затем map (!! k) для получения k -го элемента каждого подсписка, который мы не фильтруем.

Итак, мы можем написать функцию: 

kThPascalTriangle :: Num n => Int -> [n]
kThPascalTriangle k = map (!! k) (drop k pascalTriangle)
0 голосов
/ 03 мая 2018

Чтобы получить k-ую строку: 

>>> pascal_infinite !! 4
[1,4,6,4,1]

Чтобы получить все строки из [0..k]: 

>>> map (pascal_infinite !!) [0..4]
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Чтобы получить все строки из [0..k] fast : 

>>> take (4+1) pascal_infinite
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Упс, неправильно прочитал вопрос. Чтобы получить то, что вы просите, вам, вероятно, следует создать просто старую добрую формулу n choose k или что-то подобное, если вы беспокоитесь о скорости.

Если это просто упражнение, независимо от скорости, вот один из способов: 

pascal n = map (!! n) $ drop n pascal_infinite

Затем просто сэмплируйте пару из 4-х элементов: 

>>> take 8 $ pascal (4-1)
[1,4,10,20,35,56,84,120]
...