How to write a recursive function in Haskell that takes two lists as arguments and returns two list when a condition is met

Question

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)

Also, your type signature indicates three parameters, but the body only has two. — Fyodor Soikin
– Fyodor Soikin, Commented Sep 15, 2022 at 19:18
@FyodorSoikin, 1) s:os & ps are supposed to be lists (or strings). 2) I mean to say that input = string string and output = string string . Should I write it differently? — Energizer1
– Energizer1, Commented Sep 15, 2022 at 19:21
For your example, list1= "abcdef". list2= "def", what should be the output? Could you give more examples with indata and outdata? — md2perpe
– md2perpe, Commented Sep 15, 2022 at 19:34
That's not possible. Every function takes a single input and returns a single output. It is possible to create the appearance of a function that takes multiple inputs by using functions whose output is another function, but there is strictly speaking no way to return two things. You need to combine your desired outputs into a single output, such as a (String, String) tuple. — OpenAI was the last straw
– OpenAI was the last straw, Commented Sep 15, 2022 at 19:34

K. A. Buhr · Accepted Answer · 2022-09-15 20:53:41Z

0

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.

edited Sep 15, 2022 at 20:53

answered Sep 15, 2022 at 19:43

K. A. Buhr

52.7k3 gold badges56 silver badges82 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Energizer1 Over a year ago

As you said, I would like to call this in another function. "isMatch :: String -> String -> Bool". Defined as: isMatch (s : os) (p : ps). Thus, something like isMatch (isEqual ), how should I do this? When typing isMatch (fst(isEqual s:os ps) snd(isEqual s:os ps)) I get an error. Couldn't match expected type ‘Bool’ with actual type ‘String -> Bool’ • Probable cause: ‘isMatch’ is applied to too few arguments

Energizer1 Over a year ago

nvm, solved it with: (let (lst1, lst2) = isEqual (s : os) ps in isMatch lst1 lst2)

Collectives™ on Stack Overflow

How to write a recursive function in Haskell that takes two lists as arguments and returns two list when a condition is met

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related