4

:: [(Integer, Integer)]创建一个包含形式对的无限列表对(m,n)，其中 m 和 n 中的每一个都是 的成员[0 ..]。另一个要求是，如果(m,n) 是列表的合法成员，(elem (m,n) pairs)则应True在有限时间内返回。违反此要求的对的实现被视为非解决方案。

****新鲜编辑感谢您的意见，让我们看看我是否可以取得一些进展****

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

像这样的东西？我只是不知道它会在有限的时间内返回 True 。

我觉得这个问题的措辞 elem 不一定是我回答的一部分。只要你调用(elem (m,n) pairs)它就应该返回true。听起来对吗？

4

4 回答 4

8

忽略该helper方法，您拥有的列表理解将列出所有对，但元素的顺序是一个问题。您将拥有无限多对 like (0, m)，然后是无限多对 like (1, m)。当然elem将永远迭代所有(0, m)从未到达的对(1, m)等(2, m)。

我不确定你为什么有这个helper方法——有了它，你只是在构建一个配对列表，[(0,0), (1,1), (2,2), ...]因为你已经过滤了m = n. 那是要求的一部分吗？

就像@hammar 建议的那样，从 (m, n) 对开始0 = m + n并列出。然后列出对 (m, n) 其中1 = m + n。然后您的列表将如下所示[(0,0), (0,1), (1,0), (0,2), (1,1), (2,0), ...]。

于 2013-03-23T06:58:42.013 回答
1

辅助函数确保pairs 是一个形式的列表[ (0,0) , (1,1) , (2,2) ... ]。

所以elem ( m , n )对可以实现为：

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

这是一个恒定时间的实现。

于 2013-03-23T06:32:12.653 回答
1

我第一次发帖

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

我相信这回答了教授设定的三个条件。但是hammar指出，如果我选择这个列表作为答案，即形式为(t, t+1)的对的列表，那么我还不如选择列表

repeat [(0,0)]

好吧，这两个似乎都回答了教授的问题，考虑到似乎没有提到列表必须包含[0..] 和 [0..] 的所有组合。

除此之外，hammer 帮助我了解如何列出所有组合，通过从有限列表构建无限列表来促进有限时间内对 elem 的评估。这里还有另外两个有限列表——没有 Hammar 对对角线的建议那么简洁——它们似乎构建了 [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)]

它构建了长度为“大小”平方的顺时针螺旋，叠加在 hammar 的对角线算法上。

于 2013-03-23T12:45:53.090 回答
0

我相信您的任务的解决方案是：

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

于 2020-05-22T18:10:02.263 回答