CODEWITHSUNDEEP
haskellsubstitution
froehli
froehli

Reputation: 944

Step by Step Substitution

I have problems in understanding the following function

lines :: String -> [String]
lines ""        = []
lines ('\n':cs) = "": lines cs
lines (c:cs)    = case lines cs of
                   [] -> [[c]]
                   (l:ls) -> (c:l):ls

I want to understand what the function is doing when it is called by "f\no". I am looking for a tool that shows every substitution step for a better understanding of the function. I tried it manually (and got a solution while writing this post) but I am not sure if I am correct.

lines ('f':"\no")  = case lines "\no" of
                      [] -> [['f']]
                      (l:ls) -> ('f':l):ls

--> lines "\no"

lines ('\n':"o")   = "": lines "o"

--> lines "o"

lines ('o':"")     = case lines "" of
                      [] -> [['o']]
                      (l:ls) -> ('o':l):ls

--> lines "" 

lines ""           = []

--> return []

lines ('o':"")     = case [] of
                      [] -> [['o']]
lines ('o':"")     = [['o']]

--> return ["o"]

lines ('\n':cs)     = "": ["o"]

-->return "": ["o"]

lines ('f':"\no")  = case "":["o"] of
                      (l:ls) -> ('f':l):ls

lines ('f':"\no")  = ('f':""):["o"]
                   = ["f", "o"]

Is that right?

Upvotes: 1

Views: 137

Answers (3)

גלעד ברקן
גלעד ברקן

Reputation: 23945

nu, the recursive calls to lines will stack so the expression will be processed from right to left, returning the arguments to the earlier calls. Something like:

"o" will pass a "" as cs returning a []

'o' will then become ["o"] returning a (l:ls)

"\n" will become a "", cons'd into the ["o"], returning ["","o"], another (l:ls)

'f' will finally become the c in (c:l):ls meaning ('f':""):["o"] producing ["f","o"]

Upvotes: 1

Damien
Damien

Reputation: 300

I would suggest you use Debug.Trace.trace in your code to trace calls and return values:

trace :: String -> a -> a

For example:

import Debug.Trace

traceL l t v = trace (replicate l ' '++t) v  

lines' :: String -> Int -> [String]
lines' ""        l = traceL l"lines \"\" = " $ traceL l "[]" []
lines' ('\n':cs) l = 
    let v = (traceL l ("lines ('\\n':"++show cs++") = ") ""):lines' cs (l+1)
    in  (traceL l (show v) v)

lines' (c:cs) l = 
    let v = case traceL l ("lines ("++show c++":"++show cs++") = ") $ lines' cs (l+1) of [] -> [[c]];(x:xs) -> (c:x):xs
    in (traceL l (show v) v)

The l parameter is the level of call. Hope it will help

Upvotes: 2

TobiMcNamobi
TobiMcNamobi

Reputation: 4813

I tried to figure it out in my head without reading your solution. When I was half through I got a headache and started further reading your post. As far as I got all was in accord with what you wrote. The remaining part was nicely explained by you.

From what I can tell and to answer your question, yes, you are right.

Upvotes: 2

Related Questions