Обобщающая проблема Haskell (включая понимание списков)

Допустим, я хочу знать все точки на плоскости (x, y), которые находятся в прямоугольнике has.

Я могу рассчитать это, используя List Comprehension, следующим образом:

let myFun2D = [(x, y) | x <- [0..2], y <- [0..2]]

Теперь, если я хочу сделать то же самое для пространства (x, y, z), я могу пойти тем же путем и сделать:

let myFun3D = [(x, y, z) | x <- [0..2], y <- [0..2], z <- [0..2]]

Есть ли способ обобщить это для любого количества измерений? Если да, то как?

let myFunGeneralized = ?

Спасибо


list-comprehension haskell
person devoured elysium    schedule 18.09.2010    source источник

Ответы (3)


arrow_upward
11
arrow_downward

К сожалению, поскольку [(a,a)] и [(a,a,a)] и т. д. относятся к разным типам, вы не можете написать одну функцию, представляющую их все.

В любом случае, вы могли бы использовать

Prelude> let x = [0..2]
Prelude> import Control.Applicative 
Prelude Control.Applicative> (,,) <$> x <*> x <*> x
[(0,0,0),(0,0,1),(0,0,2),(0,1,0),(0,1,1),(0,1,2),(0,2,0),(0,2,1),(0,2,2),(1,0,0),(1,0,1),(1,0,2),(1,1,0),(1,1,1),(1,1,2),(1,2,0),(1,2,1),(1,2,2),(2,0,0),(2,0,1),(2,0,2),(2,1,0),(2,1,1),(2,1,2),(2,2,0),(2,2,1),(2,2,2)]

Если вместо этого вы хотите [[a]], для этого есть очень простая функция:

Prelude> sequence (replicate 3 x)
[[0,0,0],[0,0,1],[0,0,2],[0,1,0],[0,1,1],[0,1,2],[0,2,0],[0,2,1],[0,2,2],[1,0,0],[1,0,1],[1,0,2],[1,1,0],[1,1,1],[1,1,2],[1,2,0],[1,2,1],[1,2,2],[2,0,0],[2,0,1],[2,0,2],[2,1,0],[2,1,1],[2,1,2],[2,2,0],[2,2,1],[2,2,2]]

или (спасибо sdcvvc)

Prelude> import Control.Monad
Prelude Control.Monad> replicateM 3 x
[[0,0,0],[0,0,1],[0,0,2],[0,1,0],[0,1,1],[0,1,2],[0,2,0],[0,2,1],[0,2,2],[1,0,0],[1,0,1],[1,0,2],[1,1,0],[1,1,1],[1,1,2],[1,2,0],[1,2,1],[1,2,2],[2,0,0],[2,0,1],[2,0,2],[2,1,0],[2,1,1],[2,1,2],[2,2,0],[2,2,1],[2,2,2]]
person kennytm    schedule 18.09.2010
comment
Итак, поскольку есть экземпляры Eq, определенные для кортежей до 15, заставить вашу функцию работать не должно быть так сложно. - person fuz; 18.09.2010
comment
@FUZxxl: Да, но для списка кортежей все еще нужно написать 15 различных реализаций. - person kennytm; 18.09.2010
comment
Последовательность как оператор перестановки: это так элегантно! - person Paul Johnson; 18.09.2010
comment
@Paul Johnson: я бы назвал это декартовым оператором произведения, а не оператором перестановки ... но да, это действительно элегантно. :) - person Martin Jonáš; 18.09.2010
comment
sequence (replicate 3 x) можно также написать replicateM 3 x - person sdcvvc; 19.09.2010

arrow_upward
2
arrow_downward

Проблема со списком в кортеже может быть решена с помощью Template Haskell следующим образом (работает ghci -XTemplateHaskell):

> import Language.Haskell.TH
> let x = [0..2]
> let tt n l = listE [tupE [[|l!!i|] | i <- [0..(n-1)]] | l <- sequence $ replicate n l ]
> $(tt 2 x)
[(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)]
> $(tt 3 x)
[(0,0,0),(0,0,1),(0,0,2),(0,1,0),(0,1,1),(0,1,2),(0,2,0),(0,2,1),(0,2,2),(1,0,0),(1,0,1),(1,0,2),(1,1,0),(1,1,1),(1,1,2),(1,2,0),(1,2,1),(1,2,2),(2,0,0),(2,0,1),(2,0,2),(2,1,0),(2,1,1),(2,1,2),(2,2,0),(2,2,1),(2,2,2)]
person Daniel    schedule 18.09.2010

arrow_upward
1
arrow_downward

Вы можете использовать что-то вроде этого:

myFun :: Integer -> [[Integer]] -- Param: number of dimensions
myFun dim = snd $
  until ((== 0) . fst) --recursive build your tuple
  (\(d,lst) -> (pred d,[x:l|x <- [0..2],l <- lst]))
  (dim,[[]])

Это даст вам список списков точек, вы можете предположить, что все эти подсписки имеют одинаковую длину. Это должно работать так:

> myFun 0
  []
> myFun 1
  [[0],[1],[2]]
> myFun 2
  [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]
person fuz    schedule 18.09.2010
comment
Первая реализация содержала ошибку (я делал (dim,[]) вместо (dim,[[]])), но теперь она работает. - person fuz; 18.09.2010