CODEWITHSUNDEEP
listhaskellconcatenation
user3310334
user3310334

Reputation:

Concatenate (++) lists without overlap

Imagine I have two lists:

l1 = "Hey there"
l2 = "there is a turtle"

how do I "concatenate" the lists but remove the start of the second list that matches the end of the first?

magic l1 l2 == "Hey there is a turtle"

More examples,

magic "What's going on" "ing on in the world" == "What's going on in the world"
magic [1,2,3,2] [2,3,2,1] == [1,2,3,2,1]
magic [1..10] [5..20] == [1..20]
magic [1,2] [1,2] == []

What I'm looking for is something that will concatenate the lists and then remove the parts - only at the "joint" - where the lists matched up.

Things I've looked at:

I've also looked through the entire Data.List module, and couldn't find anything that does what I want out of the box.

Thus it looks like it's necessary to make our own function to do this, in which case a Prelude-function solution is preferable over something with dependencies.

Upvotes: 2

Views: 151

Answers (3)

mb21
mb21

Reputation: 39199

Since noone wrote this one up yet:

import Data.List (isPrefixOf)

magic xs ys = s' ++ r'
  where
    (s', r') = go xs
    go []    = ([], [])
    go (x:xs)
      | isPrefixOf (x:xs) ys = ([], ys)
      | otherwise            = (x:s, r)
        where
          (s, r) = go xs

Upvotes: 0

user7418640
user7418640

Reputation: 21

Here's a simple recursive solution:

magic x y = f x y y
  where f [] y z = y
        f x [] z = x
        f (x:xs) (y:ys) z = x : if x == y then f xs ys z else f xs z z

Upvotes: 2

user3310334
user3310334

Reputation:

I found a way to do it:

import Data.List
overlap xs ys = xs ++ (ys \\ (head ((tails xs) `intersect` (inits ys))))

but I don't find it very attractive and am hoping someone can improve upon it.

Upvotes: 1

Related Questions