Question: Haskell longest contiguous series of elements in a list

Question

Haskell longest contiguous series of elements in a list

Answers 3
Added at 2016-12-30 02:12
Tags
Question

I'm new to functional programming and the language haskell. I'm trying to determine the length of the longest contiguous series of elements in a list depending on a predicate function. The function is looks like this:

 longestSequence :: (a -> Bool) -> [Int] -> Int

When i call it like this:

 longestSequence (\x -> x >= 10) [1,44,33,22,2,3,55,66,66,77,88,99]

It should give me as solution 6.

My solution until yet is:

longestSequence :: (a -> Bool) -> [a] -> Int
longestSequence p [] = 0
longestSequence p (x:xs) 
  | (p x) = 1 + (longestSequence p xs)
  | otherwise = longestSequence p xs

Any hints or ideas of how i can solve this problem?

Answers
nr: #1 dodano: 2016-12-30 02:12

Try to factor out smaller sub-problems. For this example the general strategy might be like this:

  1. Convert the given list into a [Bool] list where an entry is True if the corresponding entry satisfies the predicate. That is write a function (Int -> Bool) -> [Int] -> [Bool]
  2. Group consecutive True and False values. That is write a function [Bool] -> [[Bool]]. You might want to look at Data.List.group.
  3. Filter out the False groups: [[Bool]] -> [[Bool]]
  4. For each of the inner lists count their length. [[Bool]] -> [Int]
  5. Find the maximum of those lengths: [Int] -> Int

Then you just have to compose those functions and you are done. For 1. and 4. you will want to use the function map :: (a -> b) -> [a] -> [b]. If you already know map, just use it. If you don't I would suggest writing that yourself as well.

Some of the type signatures for the functions that I gave are overly specific. Maybe try to generalise them a bit where you can.

nr: #2 dodano: 2016-12-30 02:12

In the guards, p x and otherwise part both has problems.

(p x) = 1 + (longestSequence p xs) is not always true, if the next element of x does not hold predict p, it can not be added 1

otherwise = longestSequence p xs is not true if the current longest sequence is longer than the remained one

A possible fix is to maintain the max length and the current length

longestSequence :: (a -> Bool) -> [a] -> Int
longestSequence p x = ls x 0 0
  where
    ls [] mx cur = max mx cur
    ls (x:xs) mx cur
        | p x = ls xs mx (cur+1)
        | otherwise = ls xs (max mx cur) 0
nr: #3 dodano: 2016-12-30 05:12

You can often use fold which is simpler than recursion, and in this case, we want to use scanl, which is just like foldl, except it keeps the entire list.

The following iterates through the list, incrementing the count for every item that matches the predicate. If it finds one that doesn't match, it resets the count back to zero. At the end, it finds the maximum of the resulting list.

longestSequence p = maximum . scanl (\count x -> if (p x) then count + 1 else 0) 0

For your example input of [1,44,33,22,2,3,55,66,66,77,88,99] and predicate of (\x -> x >= 10), the scanl will produce an output of [0,0,1,2,3,0,0,1,2,3,4,5,6]. Taking the maximum of this list gives 6, and you can see that the maximum occurs at the end of the input, and also the zeroes in the list where the predicate didn't match.

Incidentally, I wholeheartedly agree with jpath about breaking down the problem into small parts. I've seen people solve similar problems with a fold by cramming the max calculation inside the \count parameter with a tuple, but that makes it much harder to read. That's also what makes single-function recursive solutions like yours difficult to wrap your head around, by the way. Too much to keep track of at once, so it's hard to see where and how to fit in the reset-to-zero part.

Source Show
◀ Wstecz