CODEWITHSUNDEEP
haskell
sabu
sabu

Reputation: 307

Foldr Application

Recently I am trying to solve a problem using Foldr. The task is following:

In:[5,1,3,8,2,4,7,1]
Out:[16,8]

It means, I will double those element of the input list which is in the odd index position and even digit. I wrote the program without using foldr which is following:(It shows pattern match failure: head[])

findPos list elt =
  map fst $ filter ((elt==).snd) $ zip [0..] list

doublePos [] = []
doublePos (x:xs)
  | ((head(findPos xs x)`mod` 2) /= 0) && (x `mod` 2 == 0) =
      [2*x] ++ doublePos xs
  | otherwise = doublePos xs

How do I write this program using foldr?

Upvotes: 0

Views: 226

Answers (2)

dave4420
dave4420

Reputation: 47062

Why your existing code gives you a pattern match failure: doublePos [5,1,3,8,2,4,7,1] matches the second equation with x = 5 and xs = [1,3,8,2,4,7,1]. This causes head (findPos [1,3,8,2,4,7,1] 5) to be evaluated, but that reduces to head [] and you get your error.

To expand on this: what you seem to be hoping to get out of findPos is the index of the current element, relative to the start of the original list. But what you actually get out of it is the index of the next occurrence of the current element, relative to the next element... and if it doesn't occur again, you get an error.

(Using characters as list elements here to avoid confusion between list indices and list elements.)

 0   1   2   3   4   5   6   7   8   9  10     <-- indices relative to start
'H':'e':'l':'l':'o':' ':'t':'h':'e':'r':'e':[] <-- original list
     |           |
x = 'e'          |               V                 say we're here
   xs = 'l':'l':'o':' ':'t':'h':'e':'r':'e':[]     head (findPos xs x) = 6 but we wanted 1
                 |               ^
            x = 'o'                                say we're here instead
               xs = ' ':'t':'h':'e':'r':'e':[]     head (findPos xs x) = error "head []" but we wanted 4

The only way this can possibly work is if you pass the original list to findPos. But the only list you have available is that part of the original list you have not yet recursed into. Anyway, there are better ways of doing this, as seen in hammar's answer.

Upvotes: 2

hammar
hammar

Reputation: 139920

foldr isn't really a good choice for this function, as you need to pass the parity of the index of each element from the front of the list.

A list comprehension is probably the cleanest:

doublePos xs = [2*x | (i,x) <- zip [0..] xs, even x, odd i]

or you could use plain old recursion:

doublePos' (_:x:xs)
  | even x    = (2*x) : doublePos' xs
  | otherwise =         doublePos' xs
doublePos' _ = []

Though, if you must use foldr, you can do it by having the accumulator be a function which takes the parity of the current index as an argument:

doublePos'' xs = foldr step (const []) xs False where
  step x next p
    | p && even x = 2*x : next (not p)
    | otherwise   = next (not p)

Upvotes: 5

Related Questions