代码之家 › 专栏 › 技术社区 › yhylord

无法在Haskell中形成元组列表

tuples haskell

yhylord · 技术社区 · 7 年前

所以我的代码尝试读取 Int 并将其转换为列表:

import Control.Monad (forM, forM_)
import Data.Function (on)
import Data.List     (nub)

main = do
    t <- readLn
    forM_ [1..t] (\_ -> do
        n <- readLn
        points <- forM [1..n] (\_ -> do
            pointStr <- getLine
            let [x, y] = map read $ words pointStr
            return (x, y))
        putStrLn $ if check points then "YES" else "NO")

check :: [(Int, Int)] -> Bool
check points = ((==) `on` length) (nub $ map fst points) points

然而,GHC抱怨说

   â¢ Couldn't match type â(Int, Int)â with âIntâ
     Expected type: [Int]
       Actual type: [(Int, Int)]
   â¢ In the second argument of â(==) `on` lengthâ, namely âpointsâ
     In the expression: ((==) `on` length) (nub $ map fst points) points
     In an equation for âcheckâ:
       check points = ((==) `on` length) (nub $ map fst points) points
     |
  16 | check points = ((==) `on` length) (nub $ map fst points) points
     |                                                          ^^^^^^

我尝试在周围添加类型声明 read ,但这也不起作用。如果我更换 return (x, y) 具有 return x ,我得到了相同的错误。GHC似乎认识到 (x, y) 作为 内景 而不是 (Int, Int) 。

有什么帮助吗?

2 回复 | 直到 7 年前

Thomas M. DuBuisson 7 年前

您的问题不是形成列表-错误显示第16行,这是检查功能。我们看到:

check :: [(Int, Int)] -> Bool
check points = ((==) `on` length) (nub $ map fst points) points

请注意等式函数的类型:

((==) `on` length) :: Foldable t => t a -> t a -> Bool

因此,您需要提供两个相同类型的参数(高级注意: on 需要使用RankNTypes来允许长度应用于不同类型的参数)。但是,您提供了两种不同类型的参数( [Int] 和 [(Int,Int)] )。别再装腔作势了,只需做可读的解决方案即可:

length (nub (map fst points)) == length points

duplode 7 年前

错误消息告诉您问题出在 check ,而不在 main (特别是,这与 read 或 return )。更具体地说,它表示类型不匹配发生在 (==) `on` length 。既然如此,看看 (==)`on`长度是:

GHCi> :t (==) `on` length
(==) `on` length :: Foldable t => t a -> t a -> Bool

这告诉我们两个列表必须具有相同的元素类型,而您的 检查 --ergo“无法匹配类型 (Int, Int) 具有 Int “。 on 接受单个任意投影函数( length ,因此,确保投影可应用于两个参数的唯一方法是,如果它们具有相同的类型:

GHCi> :t on
on :: (b -> b -> c) -> (a -> b) -> a -> a -> c

类型系统无法利用以下事实,即在您的特定情况下, 长 可以应用于列表,而不考虑元素类型,因此参数类型之间的差异无关紧要。

解决这个困难最简单的办法就是放弃 在…上 :

check points = length (nub (map fst points)) == length points

或者,您可以申请 map fst 在这两方面,元素值都无关紧要,除了 nub ,所以没什么区别

check points = ((==) `on` length) (nub xCoords) xCoords
    where
    xCoords = map fst points

实现相同效果的更明确方法是 void 从…起 Data.Functor ,可用于放弃列表元素:

check points = ((==) `on` length) (void . nub $ map fst points) (void points)

最后,可以选择完全切换到不同的算法。这使得改进成为可能: 检查 可以通过只运行最短的列表来执行,而不是同时运行这两个列表(使用 长 两次要求)。您可能希望尝试实现这一点。为了便于说明,这里有一个奇特的解决方案 These , the exclusive disjunction type provided by the these package 。

import Data.List (nub)
import Data.Align (align)
import Data.These (isThese)

check :: Eq a => [(a, b)] -> Bool
check pairs = null . dropWhile isThese $ align (nub . map fst $ pairs) pairs

align 可以简明扼要地描述为贪婪 zip 。有关这方面的额外评论,请参阅。 Does Haskell have a greedy zip (one preserving all elements)?