Динамически строить понимание списка в Haskell - PullRequest
Новая
       33

Динамически строить понимание списка в Haskell

3 голосов
/ 28 февраля 2010

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

Например, если у меня есть следующее: 

all_pows (a,a') (b,b') = [ a^y * b^z | y <- take a' [0..], z <- take b' [0..] ]

Я получаю то, что я после 

*Main> List.sort $ all_pows (2,3) (5,3)
[1,2,4,5,10,20,25,50,100]

Тем не менее, я бы хотел иметь что-то вроде 

all_pows [(Int,Int)] -> [Integer]

Так что я могу поддерживать N пары аргументов без построения N версий all_pows. Я все еще довольно новичок в Хаскеле, так что, возможно, я упустил что-то очевидное. Это вообще возможно?

1 Ответ

11 голосов
/ 28 февраля 2010

Магия списка монад: 

ghci> let powers (a, b) = [a ^ n | n <- [0 .. b-1]]
ghci> powers (2, 3)
[1,2,4]
ghci> map powers [(2, 3), (5, 3)]
[[1,2,4],[1,5,25]]
ghci> sequence it
[[1,1],[1,5],[1,25],[2,1],[2,5],[2,25],[4,1],[4,5],[4,25]]
ghci> mapM powers [(2, 3), (5, 3)]
[[1,1],[1,5],[1,25],[2,1],[2,5],[2,25],[4,1],[4,5],[4,25]]
ghci> map product it
[1,5,25,2,10,50,4,20,100]
ghci> let allPowers list = map product $ mapM powers list
ghci> allPowers [(2, 3), (5, 3)]
[1,5,25,2,10,50,4,20,100]

Это, вероятно, заслуживает немного большего объяснения.

Вы могли бы написать свой 

cartesianProduct :: [[a]] -> [[a]]
cartesianProduct [] = [[]]
cartesianProduct (list:lists)
  = [ (x:xs) | x <- list, xs <- cartesianProduct lists ]

такой, что cartesianProduct [[1],[2,3],[4,5,6]] ⇒ [[1,2,4],[1,2,5],[1,2,6],[1,3,4],[1,3,5],[1,3,6]].

Однако понимания и монады намеренно похожи. Стандартная прелюдия имеет sequence :: Monad m => [m a] -> m [a], и когда m является монадой списка [], она фактически делает то, что мы написали выше.

В качестве еще одного ярлыка, mapM :: Monad m => (a -> m b) -> [a] -> m [b] - это просто композиция sequence и map.

Для каждого внутреннего списка различных степеней каждой базы вы хотите умножить их на одно число. Вы можете написать это рекурсивно 

product list = product' 1 list
  where product' accum [] = accum
        product' accum (x:xs)
          = let accum' = accum * x
             in accum' `seq` product' accum' xs

или с помощью сгиба 

import Data.List
product list = foldl' (*) 1 list

но на самом деле product :: Num a => [a] -> a уже определено! Я люблю этот язык ☺☺☺

...