Haskell: лень подвержена методу разбора - PullRequest
Новая
       33

Haskell: лень подвержена методу разбора

1 голос
/ 04 марта 2012

У меня есть простая программа (это был второй вопрос по 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

Я был просто поражен тем, насколько умным был Хаскелл, когда я это написал.По какой-то причине, когда я в интерактивном режиме набирал цифры в stdin, он давал мне ответ еще до того, как я закончил!Я думал, что это ошибка, но потом я по-дурацки понял, что лень Хаскелла (я думаю?) Взяла на себя задачу решить, что после того, как я введу 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"

Ответы [ 2 ]

5 голосов
/ 04 марта 2012

Если все записи являются полными, 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 является константой (примечание: (==) работает на Maybe с) и первый элемент является Just, верните первый элемент (который уже является Maybe Ordering).В противном случае просто верните Nothing.Вы можете обойтись без вызова isJust (head orders), но добавление его должно вернуть его, как только он увидит Nothing (в противном случае, если вы дадите ему список всех Nothing s, он проверит, является ли каждый Nothing).

2 голосов
/ 04 марта 2012

Вы, вероятно, можете использовать mapMaybe из Data.Maybe.То есть поменяйте map read на mapMaybe maybeRead.mapMaybe выполняет сопоставление функции со списком, отфильтровывает Nothing и извлекает все оставшиеся значения.

...