How to write a recursive function in Haskell that takes two lists as arguments and returns two list-CodePudding

I am trying to write a function that takes two lists (list1 & list2) expressed as strings as arguments and after recursively iterating list1 and comparing a value from list2. when the value of list1 and list2 are equal, the recursion should break and return the two lists (modified).

For example. list1= "abcdef". list2= "def"

pseudo code:

for char in list1
if char==list2[0] --> [char:] list2[1:]

In the case above this would be returning: "def" "ef"

What I got so far:

isEqual :: String -> String -> String ->String
isEqual (s : os) (p : ps)
   | p /= s = isEqual os (p : ps)
   | otherwise = s:os ps

However, I get the following error message from vs-code:

• Couldn't match expected type ‘String -> String’ with actual type ‘[Char]’ Possible cause: ‘(:)’ is applied to too many arguments
In the expression: s : os ps In an equation for ‘isEqual’: isEqual (s : os) (p : ps) | p /= s = isEqual os (p : ps) | otherwise = s : os pstypecheck(-Wdeferred-type-errors)

Couldn't match expected type ‘[Char] -> [Char]’ with actual type ‘[Char]’ The function ‘os’ is applied to one argument, but its type ‘[Char]’ has none
In the second argument of ‘(:)’, namely ‘os ps’
In the expression: s : os pstypecheck(-Wdeferred-type-errors)

CodePudding user response：

Your type signature won't work. The type signature:

isEqual :: String -> String -> String -> String

describes a function that takes three input strings and produces a single output string. In order to accept two input strings and produce two output strings, you need to write something like:

isEqual :: String -> String -> (String, String)

This function will return a pair or "tuple" of two strings. This is the standard way of returning two values, and you won't find a reasonable way to return the two strings without pairing them like this.

After this change, all you need to do is adjust your otherwise case to return a pair (s:os, ps):

isEqual :: String -> String -> (String, String)
isEqual (s : os) (p : ps)
   | p /= s = isEqual os (p : ps)
   | otherwise = (s:os, ps)

This functions appears to do what you want:

λ> isEqual "abcdef" "def"
("def","ef")

When it comes time to use the result of this function call in a larger program, you can either use functions fst and snd to extract the two lists from the returned pair, or you can use pattern matching to name the two lists. For example:

main = do
  let (lst1, lst2) = isEqual "abcdef" "def"
  putStrLn $ "First list was "    show lst1
  putStrLn $ "Second list was "    show lst2

As per your follow-up comment, if you want to pass the two lists returned by isEqual to a function that takes the two lists as separate arguments, the normal way is via a let statement exactly as you discovered:

let (lst1, lst2) = isEqual (s:os) ps in isMatch ls1 lst2

Your first attempt will also work, but you need some additional parentheses to get it to parse right:

isMatch (fst (isEqual (s:os) ps)) (snd (isEqual (s:os) ps))

or even combining the two approaches:

let lsts = isEqual (s:os) ps in isMatch (fst lsts) (snd lsts)

There are a few other ways. The higher-order function uncurry "converts" a function that takes two arguments to one that takes a pair, so you can write:

(uncurry isMatch) (isEqual (s:os) ps)
^^^^^^^^^^^^^^^^^
     `-- this function takes the pair directly

or, with the extraneous parentheses removed:

uncurry isMatch (isEqual (s:os) ps)

Again, these are just some alternatives. I think the solution you found with let is the clearest.