haskell бесконечный список инкрементных пар

Question

Создайте бесконечный список пар:: [(Integer, Integer)], содержащий пары вида (m, n), где каждый из m и n является членом [0 ..]. Дополнительным требованием является то, что если (m, n) является законным членом списка, то (elem (m, n) пар) должны вернуть True за конечное время. Реализация пар, которая нарушает это требование, считается нерешенной.*Fresh edit Спасибо за комментарии, давайте посмотрим, смогу ли я добиться прогресса*

    pairs :: [(Integer, Integer)]
    pairs = [(m,n) | t <- [0..], m <- [0..], n <-[0..], m+n == t]

Что-то вроде этого? Я просто не знаю, куда это вернет Истину за конечное время.

Я чувствую, как вопрос сформулирован, но элемент не должен быть частью моего ответа. Просто если вы вызываете (elem (m, n) пар), он должен вернуть true. Звучит правильно?

Answer 1

Игнорирование helper метод, понимание списка у вас перечислит все пары, но порядок элементов является проблемой. У вас будет бесконечно много пар, таких как (0, m) которые следуют бесконечно много пар, таких как (1, m), Конечно elem будет вечно повторять все (0, m) пары никогда не доходят (1, m) или же (2, m) и т.п.

Я не уверен, почему у вас есть helper метод - с его помощью вы только строите список пар, как [(0,0), (1,1), (2,2), ...] потому что вы отфильтровали m = n, Это было частью требований?

Как предложил @hammar, начните с 0 = m + n и перечислите пары (m, n). Затем перечислите пары (m, n), где 1 = m + n, Тогда ваш список будет выглядеть [(0,0), (0,1), (1,0), (0,2), (1,1), (2,0), ...],

Answer 2

Вспомогательная функция гарантирует, что пары является списком вида [ (0,0) , (1,1) , (2,2) ... ],

Так elem ( m , n ) пары могут быть реализованы как:

elem (m , n) _ |  m == n    = True
               |  otherwise = False

Это постоянная реализация времени.

Answer 3

Я впервые опубликовал

Prelude> let pairs = [(m, n) | t <- [0..]
                     , let m = head $ take 1 $ drop t [0..] 
                     , let n = head $ take 1 $ drop (t + 1) [0..]]

Который, я полагал, отвечал трем условиям, установленным профессором. Но Хаммар указал, что если бы я выбрал этот список в качестве ответа, то есть список пар вида (t, t+1), то я мог бы также выбрать этот список

repeat [(0,0)] 

Что ж, оба они, похоже, отвечают на вопрос профессора, учитывая, что, похоже, нет упоминания о том, что список должен содержать все комбинации [0..] и [0..].

Помимо этого, молот помог мне увидеть, как вы можете составить список всех комбинаций, упрощая оценку элементов за конечное время, создавая бесконечный список из конечных списков. Вот два других конечных списка - менее сжатых, чем предложение диагоналей Хаммара - которые, кажется, строят все комбинации [0..] и [0..]:

edges = concat [concat [[(m,n),(n,m)] | let m = t, n <- take m [0..]] ++ [(t,t)] 
      | t <- [0..]]


*Main> take 9 edges
[(0,0),(1,0),(0,1),(1,1),(2,0),(0,2),(2,1),(1,2),(2,2)]

которые строят ребра (t, 0..t) (0..t, t), и

oddSpirals size = concat [spiral m size' | m <- n] where
  size' = if size < 3 then 3 else if even size then size - 1 else size
  n = map (\y -> (fst y * size' + div size' 2, snd y * size' + div size' 2)) 
          [(x, t-x) | let size' = 5, t <- [0..], x <- [0..t]]
  spiral seed size = spiral' (size - 1) "-" 1 [seed]
  spiral' limit op count result
    | count == limit =
       let op' = if op == "-" then (-) else (+)
           m = foldl (\a b -> a ++ [(op' (fst $ last a) b, snd $ last a)]) result (replicate count 1)
           nextOp = if op == "-" then "+" else "-"
           nextOp' = if op == "-" then (+) else (-)
           n = foldl (\a b -> a ++ [(fst $ last a, nextOp' (snd $ last a) b)]) m (replicate count 1)
           n' = foldl (\a b -> a ++ [(nextOp' (fst $ last a) b, snd $ last a)]) n (replicate count 1)
       in n'
    | otherwise      =
        let op' = if op == "-" then (-) else (+)
            m = foldl (\a b -> a ++ [(op' (fst $ last a) b, snd $ last a)]) result (replicate count 1)
            nextOp = if op == "-" then "+" else "-"
            nextOp' = if op == "-" then (+) else (-)
            n = foldl (\a b -> a ++ [(fst $ last a, nextOp' (snd $ last a) b)]) m (replicate count 1)
        in spiral' limit nextOp (count + 1) n


*Main> take 9 $ oddSpirals 3
[(1,1),(0,1),(0,2),(1,2),(2,2),(2,1),(2,0),(1,0),(0,0)]

которые строят спирали по часовой стрелке с длиной "квадрат", наложенные на алгоритм диагоналей Хаммара.

Answer 4

Я считаю, что решение вашей задачи:

pairs = [(x,y) | u <- [0..], x <- [0..u], y <-[0..u] , u == x+y]