CODEWITHSUNDEEP
haskell
Waqas
Waqas

Reputation: 639

How can I iterate over a string without recursion?

isTogether' :: String -> Bool
isTogether' (x:xs) = isTogether (head xs) (head (tail xs))

For the above code, I want to go through every character in the string. I am not allowed to use recursion.

Upvotes: 1

Views: 3721

Answers (3)

ДМИТРИЙ МАЛИКОВ
ДМИТРИЙ МАЛИКОВ

Reputation: 22000

isTogether' (x:xs) = isTogether (head xs) (head (tail xs))

If I've got it right, you are interested in getting consequential char pairs from some string. So, for example, for abcd you need to test (a,b), (b,c), (c,d) with some (Char,Char) -> Bool or Char -> Char -> Bool function.

Zip could be helpful here:

> let x = "abcd"
> let pairs = zip x (tail x)
it :: [(Char, Char)]

And for some f :: Char -> Char -> Bool function we can get uncurry f :: (Char, Char) -> Bool.

And then it's easy to get [Bool] value of results with map (uncurry f) pairs :: [Bool].

Upvotes: 5

Daniel Lyons
Daniel Lyons

Reputation: 22803

To do this without recursion, you will need to use a higher order function or a list comprehension. I don't understand what you're trying to accomplish so I can only give generic advice. You probably will want one of these:

map :: (a -> b) -> [a] -> [b]

Map converts a list of one type into another. Using map lets you perform the same action on every element of the list, given a function that operates on the kinds of things you have in the list.

filter :: (a -> Bool) -> [a] -> [a]

Filter takes a list and a predicate, and gives you a new list with only the elements that satisfy the predicate. Just with these two tools, you can do some pretty interesting things:

import Data.Char

map toUpper (filter isLower "A quick test") -- => "QUICKTEST"

Then you have folds of various sorts. A fold is really a generic higher order function for doing recursion on some type, so using it takes a bit of getting used to, but you can accomplish pretty much any recursive function on a list with a fold instead. The basic type of foldr looks like this:

foldr :: (a -> b -> b) -> b -> [a] -> b

It takes three arguments: an inductive step, a base case and a value you want to fold. Or, in less mathematical terms, you could think of it as taking an initial state, a function to take the next item and the previous state to produce the next state, and the list of values. It then returns the final state it arrived at. You can do some pretty surprising things with fold, but let's say you want to detect if a list has a run of two or more of the same item. This would be hard to express with map and filter (impossible?), but it's easy with recursion:

hasTwins :: (Eq a) => [a] -> Bool
hasTwins (x:y:xs) | x == y    = True
hasTwins (x:y:xs) | otherwise = hasTwins (y:xs)
hasTwins _                    = False

Well, you can express this with a fold like so:

hasTwins :: (Eq a) => [a] -> Bool
hasTwins (x:xs) = snd $ foldr step (x, False) xs
  where
    step x (prev, seenTwins) = (x, prev == x || seenTwins)

So my "state" in this fold is the previous value and whether we've already seen a pair of identical values. The function has no explicit recursion, but my step function passes the current x value along to the next invocation through the state as the previous value. But you don't have to be happy with the last state you have; this function takes the second value out of the state and returns that as the overall return value—which is the boolean whether or not we've seen two identical values next to each other.

Upvotes: 1

Tikhon Jelvis
Tikhon Jelvis

Reputation: 68172

In Haskell, a String is just a list of characters ([Char]). Thus, all of the normal higher-order list functions like map work on strings. So you can use whichever higher-order function is most applicable to your problem.

Note that these functions themselves are defined recursively; in fact, there is no way to go through the entire list in Haskell without either recursing explicitly or using a function that directly or indirectly recurses.

Upvotes: 5

Related Questions