Is there a standard way to match 2 lists with a custom matching function in Haskell?

Question

I know that a standard way would be

(Eq z) => matchLists :: [x] -> [x] -> Bool
matchLists xs ys = xs == ys

But I have a special matching function for element which is passed from the outside and I have no control over it.

So what I am looking for is

matchLists :: (x -> x -> Bool) -> [x] -> [x] -> Bool

(Hoogle says no)

Would you end up with a custom function with a signature like this or what would you do instead?

EDIT:

zip functions don't do what I need since the resulting list has the minimal length out of 2 input lists

EDIT:

What do you think of this?

--matchListsWith :: (a -> a -> Bool) -> [a] -> [a] -> Bool
matchListsWith :: (a -> b -> Bool) -> [a] -> [b] -> Bool
matchListsWith _ [] [] = True
matchListsWith _ (_:_) [] = False
matchListsWith _ [] (_:_) = False
matchListsWith matcher (x:xs) (y:ys) = matcher x y && matchListsWith matcher xs ys

There's no reason for `matchListsWith` not to have the more general type `(a -> b -> Bool) -> [a] -> [b] -> Bool`. — Cirdec, Nov 05 '13 at 18:28

J. Abrahamson · Answer 1 · 2013-11-05T19:44:30.553

Using Data.Align we can handle both the zipping and the length issues at once

matchWith :: (a -> b -> Bool) -> [a] -> [b] -> Bool
matchWith f as bs = and $ alignWith combiner as bs where
  combiner = these (const False) (const False) f

This unfolds to the same code as your explicitly recursive function, but using tags from Data.These to mark the various list alignments. It also generalizes to many other structures like Trees or Sequences if you generalize the and.

matchWith :: (Foldable f, Align f) => (a -> b -> Bool) -> f a -> f b -> Bool
matchWith f as bs = Foldable.and $ alignWith combiner as bs where
  combiner = these (const False) (const False) f

data Tree a = Tip | Branch a (Tree a) (Tree a) deriving ( Functor, Foldable )

instance Align Tree where
  nil = Tip
  align Tip Tip = Tip
  align (Branch a la ra) Tip = Branch (This a) (fmap This la) (fmap This ra)
  align Tip (Branch b lb rb) = Branch (That b) (fmap That lb) (fmap That rb)
  align (Branch a la ra) (Branch b lb rb) =
    Branch (These a b) (align la lb) (align ra rb)

So that we have

λ> matchWith (==) Tip Tip
True
λ> matchWith (==) (Branch 3 Tip Tip) (Branch 3 Tip Tip)
True
λ> matchWith (==) (Branch 3 Tip Tip) (Branch 3 Tip (Branch 3 Tip Tip))
False

(Might as well...)

instance Eq a => Eq (Tree a) where (==) = matchWith (==)

score 4 · Answer 2 · answered Nov 05 '13 at 19:51

The hand-written approach is perfectly fine here, I think. If you're not already using some library that happens to have a suitable function for this problem, then I believe it isn't worth adding another dependency just for the sake of shaving off three lines of code.

You can still shave off a single line though:

matchListWith :: (a -> b -> Bool) -> [a] -> [b] -> Bool
matchListWith f (x:xs) (y:ys) = f x y && matchListWith f xs ys
matchListWith _ []     []     = True
matchListWith _ _      _      = False

score 1 · Answer 3 · answered Nov 05 '13 at 17:03

1

One possibility:

matchList f xs ys = and $ zipWith f xs ys

answered Nov 05 '13 at 17:03

Arjan

19,957
2
55
48

2

This might cause surprising behaviour if the lists have different lengths. `and $ zipWith (==) [1] [1,2]` evaluates to `True`. – duplode Nov 05 '13 at 17:18
That's what I thought too. I don't want it to be True. So I guess I need to keep looking. – Trident D'Gao Nov 05 '13 at 17:21

Is there a standard way to match 2 lists with a custom matching function in Haskell?

3 Answers3