Haskell类型不匹配错误：预期类型‘Bool’与实际类型‘a -> Bool’——最长递增前缀函数实现求助

Let's break down what's going wrong with your code first, then walk through straightforward, correct implementations.

The Root Cause of the Type Error #

Your lambda (\y z -> f y <= f z) expects two arguments, but takeWhile only accepts a predicate that takes one argument (its type is (a -> Bool) -> [a] -> [a]). takeWhile checks each element in isolation against the predicate, but we need to compare adjacent elements after applying f to ensure the sequence is strictly increasing. That's why you're hitting a type mismatch.

Also, note the problem specifies a strictly increasing sequence—your current code uses <=, which would allow non-strict increases, but the examples require strict growth.

Correct Implementations #

Recursive Approach (Most Intuitive) #

We can build the prefix recursively by keeping track of the last transformed value, adding elements to the prefix only if their transformed value is strictly larger than the last one:

longestAscendingPrefix :: Ord b => (a -> b) -> [a] -> [a]
longestAscendingPrefix _ [] = []
longestAscendingPrefix f (x:xs) = x : go (f x) xs
  where
    go _ [] = []
    go lastTransformed (y:ys)
      | f y > lastTransformed = y : go (f y) ys
      | otherwise = []

Testing this against your examples:

• longestAscendingPrefix (mod 5) [1..10]: The transformed values are 1,2,3,4,0,1,.... We stop at 4 because 0 isn't greater than 4, so we get [1,2,3,4] as expected.
• longestAscendingPrefix odd [1,4,2,6,8,9,3,2,1]: Transformed values are True, False, True, .... False isn't greater than True, so we only keep [1]—which matches the example.

Idiomatic Haskell with Standard Functions #

If you prefer using built-in functions, we can pair the list with its tail to check adjacent elements directly:

longestAscendingPrefix :: Ord b => (a -> b) -> [a] -> [a]
longestAscendingPrefix _ [] = []
longestAscendingPrefix f xs = 
  let adjacentPairs = zip xs (tail xs)
      validPairs = takeWhile (\(prev, curr) -> f prev < f curr) adjacentPairs
  in head xs : map snd validPairs

How this works:

1. zip xs (tail xs) creates pairs like (x1,x2), (x2,x3), ... to compare each element with the next.
2. takeWhile keeps only pairs where the transformed value of the first element is strictly less than the second.
3. We prepend the first element of the original list, then add the second element of each valid pair to build the full prefix.

Key Takeaways #

• takeWhile works for single-element predicates, but for sequential comparisons (like checking adjacent elements), we need to track state (e.g., the last transformed value) or use paired lists.
• Always double-check the problem's requirements: this task needs a strictly increasing sequence, so use < instead of <=.

内容的提问来源于stack exchange，提问作者BeanieBarrow