Choose increasing sequence from a list

user_11015460 0
Viewed 109

I would like to ask how to choose increasing subsequence of elements from a list in Haskell. The rule is that in a not empty list the first element is chosen and then every element that is bigger than the previously chosen element. For example in a list [3,1,8,4,6,7,9,2,11,4,3] would be chosen sublist [3,8,9,11]. My code so far doesn't cover the problem completely:

incrSub :: Ord a => [a] -> [a]
incrSub [] = []
incrSub (x:xs) = if x < head xs then x: incrSub (xs) else incrSub (xs)
list haskell
1 Answers

Consider the evaluation of your function on the provided sample input:

  • incrSub [3, 1, 8, 4, 6, 7, 9, 2, 11, 4, 3]
  • incrSub (3 : 1 : 8 : 4 : 6 : 7 : 9 : 2 : 11 : 4 : 3 : [])
  • 3 < 1 == False → incrSub (1 : 8 : 4 : 6 : 7 : 9 : 2 : 11 : 4 : 3 : [])
  • 1 < 8 == True → 1 : incrSub (8 : 4 : 6 : 7 : 9 : 2 : 11 : 4 : 3 : [])
  • 8 < 4 == False → 1 : incrSub (4 : 6 : 7 : 9 : 2 : 11 : 4 : 3 : [])
  • 4 < 6 == True → 1 : 4 : incrSub (6 : 7 : 9 : 2 : 11 : 4 : 3 : [])
  • 6 < 7 == True → 1 : 4 : 6 : incrSub (7 : 9 : 2 : 11 : 4 : 3 : [])
  • 7 < 9 == True → 1 : 4 : 6 : 7 : incrSub (9 : 2 : 11 : 4 : 3 : [])
  • 9 < 2 == False → 1 : 4 : 6 : 7 : incrSub (2 : 11 : 4 : 3 : [])
  • 2 < 11 == True → 1 : 4 : 6 : 7 : 2 : incrSub (11 : 4 : 3 : [])
  • 11 < 4 == False → 1 : 4 : 6 : 7 : 2 : incrSub (4 : 3 : [])
  • 4 < 3 == False → 1 : 4 : 6 : 7 : 2 : incrSub (3 : [])
  • 3 < undefined == undefined → 1 : 4 : 6 : 7 : 2 : undefined

Notice the relationship between the actual result and the expected result:

input    3 : 1 : 8 : 4 : 6 : 7 : 9 : 2 : 11 : 4 : 3 : []
expected 3 :     8 :             9 :     11 :         []
actual       1 :     4 : 6 : 7 :     2 :              undefined

So this suggests a few things to look at:

  • Your condition is filtering the opposite of what you intended.

  • You are not handling the end of the list correctly. In particular, consider the case of a 1-element list incrSub [42].

  • Your code is prone to errors because you’re using head, which is a partial function. Preferring pattern-matching may help, especially if you enable warnings (e.g. passing -Wall to GHC or adding {-# GHC_OPTIONS -Wall #-} to your file). Recall that you can use nested patterns like x1 : x2 : xs to match a list of at least 2 elements x1 and x2.

Working through examples like this using equational reasoning is a very powerful debugging technique for Haskell code. You can also use property-based testing libraries like QuickCheck to identify test cases that fail. For example, it quickly identifies the minimal failing test case of singleton lists:

> import Test.QuickCheck (quickCheck)
> resultIsSorted :: [Int] -> Bool; resultIsSorted input = let { result = incrSub input } in result == sort result
> quickCheck resultIsSorted
*** Failed! Exception: 'Prelude.head: empty list' (after 2 tests and 2 shrinks):
[0]

You can write more complex properties to find more interesting edge cases.

user_2468860
Related