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

Question

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

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

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

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

Answer 1

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

Я не знаю, почему у вас есть метод helper - с ним, вы только строит список пар, как [(0,0), (1,1), (2,2), ...], потому что вы» ve отфильтровано по 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..]] 

Который, я верил, ответил на три условия, установленные профессором. Но Хаммар отметил, что если я выбрал этот список в качестве ответа, то есть, список пар вида (т, т + 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)] 

, которые построить края (т, 0..t) (0..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)] 

которые строят по часовой стрелке спирали длиной 'размер' в квадрате, наложенные по алгоритму диагоналей хаммера.