Haskell:由解析方法影响的懒惰

Question

我有一个简单的程序(这是CCC 2012上的第二个问题),它取一个数字列表,并确定是否有任何严格增加/减少/不变的序列正在进行.例如:

1 2 3 4 7 8 => Increasing
5 1 -2 -100 => Decreasing
9 9 9 9 9 9 => Constant
1 2 3 4 5 0 => Nothing

当我对此进行编码时,我对Haskell的智能程度感到震惊.出于某种原因,当我以交互方式输入数字到stdin时,在我完成之前就给了我答案!我认为这是一个错误,但后来我愚蠢地意识到,Haskell的懒惰(我想？)正在采取独自去决定,之后我进入1,2,3,0,不管以后有什么来了,结果将是Nothing,所以它高兴地输出那个.

不幸的是,当我改变时

let readings = map (read :: (Read a, Num a) => String -> a) $ lines input

至

let readings = parse $ lines input

与parse被读取数字输入一个更安全的方法,实现为

maybeRead :: (Read a) => String -> Maybe a
maybeRead = fmap fst . listToMaybe . filter (null . dropWhile isSpace . snd) . reads

parse :: (Read a) => [String] -> [a]
parse xs =
    let entries = map maybeRead xs
    in if all isJust entries
        then map fromJust entries
        else []

它不再这样做了.

为什么？

编辑:更多代码

-- | Zip together adjacent list elements as pairs in a new list.
zipPairs :: [a] -> [(a, a)]
zipPairs xs = zip (init xs) (tail xs)

-- | Return True if all elements of a given list are equal.
constant :: (Eq a) => [a] -> Bool
constant xs = all (== head xs) (tail xs)

-- | Return the order that the elements of a list are sorted in, if they form
-- a strictly increasing (Just LT), decreasing (Just GT) or constant (Just EQ)
-- sequence. If there is no pattern, return Nothing.
order :: (Ord a) => [a] -> Maybe Ordering
order xs =
    let orders = map (\(x, y) -> x `compare` y) (zipPairs xs)
    in if constant orders then Just (head orders) else Nothing

然后在main我有

let readings = parse $ lines input
putStrLn $ if null readings
    then "bad input"
    else case order readings of
        Just EQ -> "Constant"
        Just LT -> "Diving"
        Just GT -> "Rising"
        Nothing -> "Nothing"

Answer 1

如果所有条目都是正确的,则all isJust entries检查整个条目列表,这意味着在parse返回之前需要读入整个条目列表.

好吧,为什么较长的解释orders是懒惰- all返回False只要它达到了它的谓词返回一个值False.因此,constant一旦它击中尾部中不等于头部的值,就返回false. order返回后立即constant返回,因此order是懒惰的.

我的第一个建议是风格 - 在zipWith计算时查看功能orders. let orders = zipWith compare xs $ tail xs应该同样有效.

至于解决你的实际问题,试试吧

order xs = let orders = zipWith (liftM2 compare) xs $ tail xs
           in if isJust (head orders) && constant orders
              then head orders
              else Nothing

请注意,您需要导入 Data.Monad

liftM2 compare将Just (compare x y)在传递时返回Just x,Just y并且Nothing如果其中一个或两个参数都是Nothing.

orders现在是一个[Maybe Ordering].如果orders是常量(注意:(==)在Maybes上工作)并且第一个元素是a Just,则返回第一个元素(已经是a Maybe Ordering).否则,只需返回Nothing.您可以在没有isJust (head orders)调用的情况下执行,但添加它应该在它看到时立即返回Nothing(否则,如果您给它一个所有Nothings 的列表,它将检查是否每个都是Nothing).