Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why doesn't this function terminate in Haskell?

Tags:

haskell

I am confused why my function nest which composes f with itself n times

nest f 0 = id
nest f n = f . nest f (n - 1)

never terminates. I would have thought that it would "pattern match" on the case when n becomes zero. I am defining it by typing these two lines into GHCI and calling with nest (+ 1) 2 3 for instance.

like image 741
Jon Deaton Avatar asked Nov 17 '19 20:11

Jon Deaton


People also ask

Does every Haskell function terminate?

This represents the fact that Haskell programs are not guaranteed to terminate and can have exceptions. I.e., all Agda programs will terminate, and a Bool in Agda corresponds to exactly {True, False} .

What does it mean for a function to terminate?

The exit() function is used to terminate a process or function calling immediately in the program. It means any open file or function belonging to the process is closed immediately as the exit() function occurred in the program.

What does >> mean in Haskell?

Essentially, a >> b can be read like "do a then do b , and return the result of b ". It's similar to the more common bind operator >>= .

How do I run a function in Haskell?

If you have installed the Haskell Platform, open a terminal and type ghci (the name of the executable of the GHC interpreter) at the command prompt. Alternatively, if you are on Windows, you may choose WinGHCi in the Start menu. And you are presented with a prompt. The Haskell system now attentively awaits your input.


2 Answers

By typing the function on two separate REPL lines, you are essentially redefining it the second time around, omitting the base case.

The correct way to enter this function into the REPL is:

nest f 0 = id; nest f n = f . nest f (n - 1)

Alternatively, you can enter multiline mode with the :{ command, and leave it using :}.

like image 95
Emily Avatar answered Oct 25 '22 13:10

Emily


When you pasted it into GHCi what you did was define one function of nest f 0 = id. Then you said "ignore that function, I'm replacing it with a new function of the same name where the whole definition is nest f n = f . nest f (n - 1).

like image 41
Thomas M. DuBuisson Avatar answered Oct 25 '22 14:10

Thomas M. DuBuisson