CODEWITHSUNDEEP
haskellfold
Tony Chamberlain
Tony Chamberlain

Reputation: 171

Converting a foldl into fold1

I am using the following fold to get the final monotonically decreasing sequence of a list.

foldl (\acc x -> if x<=(last acc) then acc ++ [x] else [x]) [(-1)] a

So [9,5,3,6,2,1] would return [6,2,1] However, with foldl I needed to supply a start for the fold namely [(-1)]. I was trying to turn into to a foldl1 to be able to handle any range of integers as well as any Ord a like so:

foldl1 (\acc x -> if x<=(last acc) then acc ++ [x] else [x]) a

But I get there error:

cannot construct infinite type: a ~ [a]
in the second argument of (<=) namely last acc

I was under the impression that foldl1 was basically :

foldl (function) [head a] a

But I guess this isn't so? How would you go about making this fold generic for any Ord type?

Upvotes: 2

Views: 100

Answers (2)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476503

I was under the impression that foldl1 was basically :

foldl (function) [head a] a

No, foldl1 is basically:

foldl function (head a) (tail a)

So the initial element is not a list of head a, but head a.

How would you go about making this fold generic for any Ord type?

Well a quick fix is:

foldl (\acc x -> if x<=(last acc) then acc ++ [x] else [x]) [head a] (tail a)

But there are still two problems:

  • in case a is an empty list, this function will error (while you probably want to return the empty list); and
  • the code is not terribly efficient since both last and (++) run in O(n).

The first problem can easily be addressed by using pattern matching to prevent that scenario. But for the latter you better would for instance use a reverse approach. Like for instance:

f :: Ord t => [t] -> [t]
f [] = [] -- case when the empty list is given
f a = reverse $ foldl (\acc@(ac:_) x -> if x <= ac then (x:acc) else [x]) [head a] (tail a)

Furthermore personally I am not a huge fan of if-then-else in functional programming, you can for instance define a helper function like:

f :: Ord t => [t] -> [t]
f [] = [] -- case when the empty list is given
f a = reverse $ foldl g [head a] (tail a)
    where g acc@(ac:_) x | x <= ac = (x:acc)
                         | otherwise = [x]

Now reverse runs in O(n) but this is done only once. Furthermore the (:) construction runs in O(1) so all the actions in g run in O(1) (well given the comparison of course works efficient, etc.) making the algorithm itself O(n).

For your sample input it gives:

*Main> f [9,5,3,6,2,1]
[6,2,1]

Upvotes: 3

Pedro Castilho
Pedro Castilho

Reputation: 10512

The type of foldl1 is:

Foldable t => (a -> a -> a) -> t a -> a

Your function argument, 

\acc x -> if x<=(last acc) then acc ++ [x] else [x]

has type:

(Ord a) => [a] -> a -> [a]

When Haskell's typechecker tries typechecking your function, it'll try unifying the type a -> a -> a (the type of the first argument of foldl1) with the type [a] -> a -> [a] (the type of your function).

To unify these types would require unifying a with [a], which would lead to the infinite type a ~ [a] ~ [[a]] ~ [[[a]]]... and so on.

The reason this works while using foldl is that the type of foldl is:

Foldable t => (b -> a -> b) -> b -> t a -> b

So [a] gets unified with b and a gets unified with the other a, leading to no problem at all.

foldl1 is limited in that it can only take functions which deal with only one type, or, in other terms, the accumulator needs to be the same type as the input list (for instance, when folding a list of Ints, foldl1 can only return an Int, while foldl can use arbitrary accumulators. So you can't do this using foldl1).

With regards to making this generic for all Ord values, one possible solution is to make a new typeclass for values which state their own "least-bound" value, which would then be used by your function. You can't make this function as it is generic on all Ord values because not all Ord values have sequence least bounds you can use.

class LowerBounded a where
    lowerBound :: a

instance LowerBounded Int where
    lowerBound = -1

finalDecreasingSequence :: (Ord a, LowerBounded a) => [a] -> [a]
finalDecreasingSequence = foldl buildSequence lowerBound
  where buildSequence acc x
    | x <= (last acc) = acc ++ [x]
    | otherwise       = [x]

You might also want to read a bit about how Haskell does its type inference, as it helps a lot in figuring out errors like the one you got.

Upvotes: 2

Related Questions