CODEWITHSUNDEEP
haskellrecursion
Leon
Leon

Reputation: 23

How to stop recursing and produce the list in memory

(1.) The function "sameString" returns a Boolean value for whether two strings are the same regardless of capitalisation.

--  *Main> sameString "HeLLo" "HElLo"
--   True
--   *Main> sameString "Hello" "Hi there"
--   False


sameString :: String -> String -> Bool
sameString str1 str2
    | length str1 == length str2 = and [ a == b | (a,b) <- zip (capitalise str1) (capitalise str2) ]
    | otherwise = False

(1) Helper function "capitalise" does the capitalising.

capitalise :: String -> String
capitalise str = [ toUpper x | x <- str ]

(2) Function "prefix" returns a Boolean value which states whether the first string is a prefix of the second, regardless of capitalisation.

--  *Main> prefix "bc" "abCDE"
--  False
--  *Main> prefix "Bc" "bCDE"
--  True

prefix :: String -> String -> Bool
prefix [] [] = True
prefix substr str
    | sameString string' substr == True = True
    | otherwise = False
    where chop_str :: String -> String -> String
          chop_str str substr = (take (length substr) str)
          string' = chop_str str substr

(3.) Function "dropUntil" returns the contents of the second string after the first occurrence of the first string. If the second string does not contain the first as a substring, it should return the empty string.

*Main> dropUntil "cd" "abcdef"
"ef"

 dropUntil :: String -> String -> String
 dropUntil substr [] = ""
 dropUntil substr (s:tr)
    | prefix substr (s:tr) == False = drop 1 s : dropUntil substr tr
    | prefix substr (s:tr) == True =

So now the question. I was thinking of doing dropUntil with recursion.

What I think the function above should do is:

1) Given a string and a substring (for which the substring is not the prefix of the string) ...

it should drop the head of the string ...

and cons the empty list "" to

... a recursive call on the remaining tail and the same substring.

The idea behind it is to keep dropping the head of the list until the substring becomes the prefix of the list, where the function should then produce the remainder of the string as a result.

However, I have no idea how to do this. What I essentially want to do is make

| prefix substr (s:tr) == True =  "leftover_string"

Where "leftover_string" is what remains after the recursive call drops the elements until the condition is met that the substring is the prefix of the remainder.

Is this possible to do the way I started?

Upvotes: 1

Views: 508

Answers (2)

CR Drost
CR Drost

Reputation: 9817

We've had a lot of questions in the past couple of days which involve running down an equatable [x] with some other [x] looking for isPrefixOf. One primitive which has emerged in my thought process since then is really valuable here:

import Data.List

splitAtSublist :: ([x] -> Bool) -> [x] -> Maybe ([x], [x])
splitAtSublist pred list = find (pred . snd) $ zip (inits list) (tails list)

The splittings zip (inits list) (tails list) for a string "abcd" look like [("", "abcd"), ("a", "bcd"), ("ab", "cd"), ("abc", "d"), ("abcd", ""))]. This finds the first element where the "tail end" of the splitting satisfies the predicate pred.

To get dropUntil s from this basis we can just do:

dropUntil p ls = 
    maybe "" (drop (length p) . snd) $ 
        splitAtSublist (p `isPrefixOf`) ls

where isPrefixOf is from Data.List too. Substituting in, we find out that we don't use the inits list at all and it just becomes:

dropUntil p = maybe "" (drop $ length p) . find (p `isPrefixOf`) . tails

which is as simple as I can get it.

Upvotes: 2

ErikR
ErikR

Reputation: 52039

Is this what you want?

| prefix substr (s:tr) == True =  drop (length substr) (s:tr)

Some notes:

You have a type error here:

| prefix substr (s:tr) == False = drop 1 s : dropUntil substr tr
                                  ^^^^^^^^

I think you just want:

| prefix substr (s:tr) == False = dropUntil substr tr

Upvotes: 0

Related Questions