Haskell: как обновлять каждую бесконечную переменную один раз в понимании списка с помощью бесконечных списков [duplicate]

Функция NumberFormatException - это то, как Java должно сказать вам: «Я попытался преобразовать String в int, и я не смог этого сделать».

В вашей трассе исключения вы можете прочитать

Exception in thread "main" java.lang.NumberFormatException: For input string: "Ace of Clubs"
    at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
    at java.lang.Integer.parseInt(Integer.java:580)
    at java.lang.Integer.parseInt(Integer.java:615)
    at set07102.Cards.main(Cards.java:68)

В основном это означает, что в строке 68 вашего кода вы вызываете метод Integer.parseInt, передавая «Ace of Clubs» в качестве пареметра. Этот метод ожидает целочисленное значение, представленное как String, например. «4», поэтому метод жалуется на исключение NumberFormatException, потому что «Ace of Clubs» вообще не кажется целым.

58
задан Rodrigo de Azevedo 16 October 2016 в 12:07
поделиться

13 ответов

Это очень легко со списком. Чтобы получить декартово произведение списков xs и ys, нам просто нужно взять кортеж (x,y) для каждого элемента x в xs и каждый элемент y в ys.

Это дает нам следующее понимание списка:

cartProd xs ys = [(x,y) | x <- xs, y <- ys]
84
ответ дан sepp2k 20 August 2018 в 06:47
поделиться
  • 1
    Спасибо, настолько простой, но элегантный, действительно помогли с другой проблемой :) – Callum Rogers 8 November 2010 в 10:20
  • 2
    Хорошо также для Эрланг, спасибо. Небольшое изменение в синтаксисе: cartProd (Xs, Ys) - & gt; [{X, Y} || X & lt; -Xs, Y & lt; -Ys]. – Dacav 31 October 2011 в 13:18

Вот моя реализация n-арного декартова произведения:

crossProduct :: [[a]] -> [[a]]
crossProduct (axis:[]) = [ [v] | v <- axis ]
crossProduct (axis:rest) = [ v:r | v <- axis, r <- crossProduct rest ]
0
ответ дан Christian Oudard 20 August 2018 в 06:47
поделиться
  • 1
    Как насчет crossProduct = sequence? – Daniel Wagner 19 April 2016 в 06:42
  • 2
    Что делать, если список пуст? Я предполагаю, что вы обнаружили неправильный базовый случай. – dfeuer 24 October 2017 в 02:53

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

Стандартный подход заключается в использовании диагонализации; записывая один вход вдоль вершины и другой вход слева, мы могли бы написать двумерную таблицу, содержащую полное декартово произведение следующим образом:

   1  2  3  4 ...
a a1 a2 a3 a4 ...
b b1 b2 b3 b4 ...
c c1 c2 c3 c4 ...
d d1 d2 d3 d4 ...

.  .  .  .  . .
.  .  .  .  .  .
.  .  .  .  .   .

Конечно, работая через любую строку даст нам бесконечно элементы до того, как он достигнет следующей строки; Подобным же образом столкновение будет катастрофическим. Но мы можем идти по диагоналям, которые идут вниз и влево, начиная снова немного дальше вправо каждый раз, когда мы достигаем края сетки.

a1

   a2
b1

      a3
   b2
c1

         a4
      b3
   c2
d1

... и так далее. В порядке, это даст нам:

a1 a2 b1 a3 b2 c1 a4 b3 c2 d1 ...

Чтобы закодировать это в Haskell, мы можем сначала написать версию, которая создает двумерную таблицу:

cartesian2d :: [a] -> [b] -> [[(a, b)]]
cartesian2d as bs = [[(a, b) | a <- as] | b <- bs]

Неэффективная метод диагонализации состоит в том, чтобы затем итерации сначала по диагоналям, а затем по глубине каждой диагонали, каждый раз вытягивая соответствующий элемент. Для простоты объяснений я предполагаю, что оба входных списка бесконечны, поэтому нам не нужно возиться с проверкой границ.

diagonalBad :: [[a]] -> [a]
diagonalBad xs =
    [ xs !! row !! col
    | diagonal <- [0..]
    , depth <- [0..diagonal]
    , let row = depth
          col = diagonal - depth
    ]

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

a1 a2 / a3 a4 ...
     /
    /
b1 / b2 b3 b4 ...
  /
 /
/
c1 c2 c3 c4 ...
---------------------------------
d1 d2 d3 d4 ...

 .  .  .  . .
 .  .  .  .  .
 .  .  .  .   .

Верхний левый треугольник будет битами, которые мы уже выбрали; верхний правый четырехугольник будет рядами, которые были частично выпущены, но все равно будут способствовать результату; а нижний прямоугольник будет строками, которые мы еще не начали испускать. Начнем с того, что верхний треугольник и верхний четырехугольник будут пустыми, а нижний прямоугольник будет всей сеткой. На каждом шаге мы можем испускать первый элемент каждой строки в верхнем четырехграннике (по существу перемещая наклонную линию на единицу), а затем добавить одну новую строку из нижнего прямоугольника в верхний четырехугольник (по существу перемещая горизонтальную линию вниз на один ).

diagonal :: [[a]] -> [a]
diagonal = go [] where
    go upper lower = [h | h:_ <- upper] ++ case lower of
        []         -> concat (transpose upper')
        row:lower' -> go (row:upper') lower'
        where upper' = [t | _:t <- upper]

Хотя это выглядит несколько сложнее, оно значительно более эффективно. Он также обрабатывает оценки, которые мы пропустили в более простой версии.

Но вы не должны писать весь этот код самостоятельно, конечно! Вместо этого вы должны использовать пакет universe . В Data.Universe.Helpers имеется (+*+) , который объединяет вышеупомянутые функции cartesian2d и diagonal, чтобы дать только декартово произведение:

Data.Universe.Helpers> "abcd" +*+ [1..4]
[('a',1),('a',2),('b',1),('a',3),('b',2),('c',1),('a',4),('b',3),('c',2),('d',1),('b',4),('c',3),('d',2),('c',4),('d',3),('d',4)]

Вы также можете сами увидеть диагонали, если эта структура станет полезна:

Data.Universe.Helpers> mapM_ print . diagonals $ cartesian2d "abcd" [1..4]
[('a',1)]
[('a',2),('b',1)]
[('a',3),('b',2),('c',1)]
[('a',4),('b',3),('c',2),('d',1)]
[('b',4),('c',3),('d',2)]
[('c',4),('d',3)]
[('d',4)]

Если у вас много списков продуктов вместе, повторение (+*+) может несправедливо предвзято относиться к определенным спискам; вы можете использовать choices :: [[a]] -> [[a]] для ваших n-мерных декартовых продуктов.

9
ответ дан Daniel Wagner 20 August 2018 в 06:47
поделиться
  • 1
    Интересно, как будет выглядеть формулировка logict. – dfeuer 24 October 2017 в 02:51

Еще один способ, используя нотацию do:

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys = do x <- xs
                    y <- ys
                    return (x,y)
10
ответ дан gawi 20 August 2018 в 06:47
поделиться

Ну, один очень простой способ сделать это будет со списком:

cartProd :: [a] -> [b] -> [(a, b)]
cartProd xs ys = [(x, y) | x <- xs, y <- ys]

Я полагаю, что я это сделаю, хотя я не специалист Haskell (каким-либо образом ).

6
ответ дан James Cunningham 20 August 2018 в 06:47
поделиться

Если ваши входные списки одного типа, вы можете получить декартово произведение произвольного количества списков, используя sequence (используя List монаду). Это даст вам список списков вместо списка кортежей:

> sequence [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
50
ответ дан JB. 20 August 2018 в 06:47
поделиться

Существует очень элегантный способ сделать это с помощью аппликативных функторов:

import Control.Applicative

(,) <$> [1,2,3] <*> [4,5,6]
-- [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

Основная идея - применить функцию к «завернутым» аргументам, например

(+) <$> (Just 4) <*> (Just 10)
-- Just 14

В случае списков функция будет применена ко всем комбинациям, поэтому все, что вам нужно сделать, это «набивать» их с помощью (,).

См. http://learnyouahaskell.com / функторы-аппликативные-функторы-моноиды # аппликативные-функторы или (более теоретические) http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf для деталей.

40
ответ дан Landei 20 August 2018 в 06:47
поделиться

Это работа для sequence ing. Монадическая реализация этого может быть:

cartesian :: [[a]] -> [[a]]
cartesian [] = return []
cartesian (x:xs) = x >>= \x' -> cartesian xs >>= \xs' -> return (x':xs')

*Main> cartesian [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]

Как вы можете заметить, это похоже на реализацию map чистыми функциями, но в монадическом типе. Соответственно, вы можете упростить его до

cartesian :: [[a]] -> [[a]]
cartesian = mapM id

*Main> cartesian [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
2
ответ дан Palec 20 August 2018 в 06:47
поделиться

Еще один способ добиться этого - использовать аппликации:

import Control.Applicative

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys = (,) <$> xs <*> ys
11
ответ дан Paul 20 August 2018 в 06:47
поделиться

Правильный способ заключается в использовании списков, как уже отмечали другие люди, но если вы хотите сделать это без использования списков по любой причине, вы можете сделать это:

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs [] = []
cartProd [] ys = []
cartProd (x:xs) ys = map (\y -> (x,y)) ys ++ cartProd xs ys
11
ответ дан Stuart Golodetz 20 August 2018 в 06:47
поделиться
  • 1
  • 2
    Вместо map (\y -> (x,y)) вы можете написать map ((,) x). – Yitz 8 November 2010 в 10:19
  • 3
    @Chuck: Nice :) Это было время для меня Haskell-wise, вот почему я ошибаюсь на стороне упрощенных решений ... – Stuart Golodetz 8 November 2010 в 13:16
  • 4
    @Yitz: Да, хороший звонок. Я забыл об этом (см. Выше в разделе «это было какое-то время») ... – Stuart Golodetz 8 November 2010 в 13:17
  • 5
    Понимание @Stuart List может быть «правильным способом». но есть ли недостатки, чтобы сделать это таким образом? Кажется, это хорошо для меня, и это помогает новичкам обдумывать простую реализацию декартовых продуктов. +1 – Landon Poch 3 August 2016 в 05:35

Как отмечают другие ответы, использование списка в списке является наиболее естественным способом сделать это в Haskell.

Если вы изучаете Haskell и хотите работать над разработкой интуиций о типах классов, таких как Monad, однако, это забавное упражнение, чтобы понять, почему это немного более короткое определение эквивалентно:

import Control.Monad (liftM2)

cartProd :: [a] -> [b] -> [(a, b)]
cartProd = liftM2 (,)

Вы, вероятно, никогда не захотели бы писать это в реальном коде, но основная идея - это то, что вы «В Haskell мы все время видим: мы используем liftM2, чтобы поднять немонодическую функцию (,) в монаду - в данном случае именно монаду списка.

Если это не сделать какой-либо смысл или не полезно, забудьте об этом - это просто еще один способ взглянуть на проблему.

51
ответ дан Travis Brown 20 August 2018 в 06:47
поделиться
  • 1
    Вероятно, хорошая идея узнать, что на самом деле делают монады: P – Callum Rogers 7 November 2010 в 23:02
  • 2
    В качестве сноски (три года спустя): теперь я предполагаю, что изначально я использовал монадическую liftM2 для ясности (больше людей слышали о монадах, чем аппликативные функторы?), Но все, что вам нужно, - это прикладной функтор экземпляр для списков, поэтому liftA2 будет работать эквивалентно. – Travis Brown 19 September 2013 в 13:27

что-то вроде:

cartProd x y = [(a,b) | a <- x, b <- y]
5
ответ дан vichle 20 August 2018 в 06:47
поделиться
0
ответ дан Manoj R 31 October 2018 в 06:05
поделиться
Другие вопросы по тегам:

Похожие вопросы: