CODEWITHSUNDEEP
listhaskellfold
anonymous
anonymous

Reputation: 29

Gap function that returns the integer distance between first appearance of two elements in a list using either foldl or foldr.(Haskell)

the type is defined as follows: gap :: (Eq a) => a -> a -> [a] -> Maybe Int I have been stuck on this problem for more than an hour and have no idea how to approach the problem. I am aware that it requires the use of fold and am familiar with that topic. Please take into consideration that either foldl or foldr must be used. The output when called ought to look like this

gap 3 8 [1..10] =Just 5

gap 8 3 [1..10] =Nothing

gap 'h' 'l' "hello" =Just 2

gap 'h' 'z' "hello" =Nothing

Upvotes: 1

Views: 297

Answers (2)

xgrommx
xgrommx

Reputation: 1

Maybe my solution isn't nice, but it works

import Control.Monad
import Data.Function
import Data.Foldable     

(...) = (.) . (.)
gap x y = liftA2 ((guard . (> 0) =<<) ... liftA2 (subtract `on` fst)) 
                 (find ((==x) . snd)) (find((==y) . snd)) . zip [0..]

Upvotes: 0

0xd34df00d
0xd34df00d

Reputation: 1505

You might dropWhile the list until you find the starting element and then fold from the right, starting with Nothing, replacing that with Just 1 once you hit the end element, and fmaping +1 to the accumulator. In code:

gap :: Eq a => a -> a -> [a] -> Maybe Int
gap from to xs = case dropWhile (/= from) xs of
                      [] -> Nothing
                      (_:rest) -> gap' to rest

gap' :: Eq a => a -> [a] -> Maybe Int
gap' to = foldr f Nothing
    where f x acc | x == to = Just 1
                  | otherwise = (+1) <$> acc

The nice thing is that it works correctly if you have several occurences of the elements in your sequence:

*Main> gap 3 8 $ [1..10] ++ [1..10]
Just 5
*Main> gap 3 8 [1, 2, 3, 3, 3, 8]
Just 3

Upvotes: 1

Related Questions