Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Trouble understanding how tuple recursion works in Haskell

I am having trouble understanding how this function works. The function is supposed to take in a string and split that string into a pair, of which the first element is the first 'word' that is in the string and the second element is the remainder of the input string.

In particular, on line 6, I understand why the function should terminate when isSpace c is true but don't understand why that should return a tuple with the first element being the empty list. I was wondering if someone could explain why this works with a relatively simple (but non-trivial) example such as nextWord "an apple".

import Data.Char
nextWord :: String -> (String, String)
nextWord []
  = ([],[])
nextWord (c:cs)
  | isSpace c = ([], cs)
  | otherwise = (c: word, other)
  where
    (word, other) = nextWord cs

EDIT: As an example of what this function returns when the given argument starts with a space, nextWord " hello" should return ("", "hello").

like image 306
SilverWay Avatar asked Dec 27 '14 18:12

SilverWay


1 Answers

Let's step through it!

nextWord "an apple"

Since "an apple" doesn't pattern match against [], we're in the second case. Substituting in 'a': "n apple" for c : cs, we get:

nextWord ('a':"n apple")
  | isSpace 'a' = ([], "n apple")
  | otherwise = ('a': word, other)
  where
    (word, other) = nextWord "n apple"

isSpace 'a' is False, so this simplifies to

nextWord ('a':"n apple") = ('a': word, other)
  where (word, other) = nextWord "n apple"

Similarly, for nextWord "n apple" we get

nextWord ('n':" apple") = ('n': word, other)
  where (word, other) = nextWord " apple"

And for nextWord " apple" we get

nextWord (' ':"apple")
  | isSpace ' ' = ([], "apple")
  | otherwise = ('a': word, other)
  where
    (word, other) = nextWord "n apple"

Which simplifies to

nextWord (' ':"apple") = ([], "apple")

Substituting back into our expression for nextWord "n apple", we get

nextWord ('n':" apple") = ('n': word, other)
  where (word, other) = ([], "apple")

which simplifies to

nextWord ('n':" apple") = ('n':[], "apple")

or

nextWord ('n':" apple") = ("n", "apple")

Now substituting that back into our expression for nextWord "an apple", we get

nextWord ('a':"n apple") = ('a': word, other)
  where (word, other) = ("n", "apple")

which simplifies to

nextWord ('a':"n apple") = ('a':"n", "apple")

or

nextWord ('a':"n apple") = ("an", "apple")
like image 59
rampion Avatar answered Oct 21 '22 12:10

rampion