Можно ли аккуратно вычислить список кубов? - PullRequest
4 голосов
/ 05 января 2011

Можно ли упростить следующую функцию с помощью функций высшего порядка, монад или чего-то еще?

cube list = [(x, y, z) | x <- list, y <- list, z <- list]

Функция просто создает список всех тройных перестановок элементов списка. Например:

> cube [1..2]
[(1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2),(2,2,1),(2,2,2)]

Ответы [ 6 ]

10 голосов
/ 05 января 2011

Исходя из ответа Билла, поскольку этот код использует монаду списка, мы можем использовать «аппликативный» стиль для «функций более высокого порядка». Является ли это хорошей идеей, оставлено в качестве упражнения для инженера.

import Control.Applicative

cube :: [a] -> [b] -> [c] -> [(a,b,c)]
cube x y z = (,,) <$> x <*> y <*> z
8 голосов
/ 05 января 2011

Хотя он дает вам списки вместо кортежей, вы можете использовать функцию sequence в Control.Monad :

> let list = [1..2]
> sequence [list, list, list]
[[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,1],[2,1,2],[2,2,1],[2,2,2]]

Функция sequence аккуратна, потому что, хотяего «предполагаемое» назначение - составить список действий, выполнить их по порядку и вернуть их результаты в виде списка, используя его в монаде списка. Комбинации предоставляются бесплатно.

> sequence $ replicate 3 "01"
["000","001","010","011","100","101","110","111"]
7 голосов
/ 05 января 2011

На самом деле, ваше понимание списка - это использование монады List.

Другой способ написать это:

cube :: [a] -> [(a,a,a)]
cube list = do
  x <- list
  y <- list
  z <- list
  return (x, y, z)
6 голосов
/ 05 января 2011

Это не очень серьезный ответ, но я все равно должен его предложить.В основном ради сумасшествия.

import Control.Monad
import Control.Monad.Instances

cube :: [a] -> [(a, a, a)]
cube = join . join $ liftM3 (,,)

Веселитесь с этим.:)

3 голосов
/ 06 января 2011

Для моделирования после того, что сделал Джои Адамс:

g>replicateM 3 [1..2]
[[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,1],[2,1,2],[2,2,1],[2,2,2]]

Для полного решения (передайте ему список и получите 3 кортежа), можно сделать что-то подобное:

g>let cube = map (\(a:b:c:_) -> (a, b, c)) . replicateM 3
cube :: [t] -> [(t, t, t)]
(0.00 secs, 526724 bytes)
g>cube [1..2]
[(1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2),(2,2,1),(2,2,2)]
it :: [(Integer, Integer, Integer)]

Но ИМХО, решение Эдварда З. Янга царит.

2 голосов
/ 06 января 2011

Кому нужны монады, если вы можете иметь биты?

import Data.Bits

cube :: [(Int,Int,Int)]
cube = map tuple [0..7] where
   tuple x = (1 + div (x .&. 4)  4, 1 + div (x .&. 2)  2, 1 + x .&. 1)
...