So at some point up in the heirarchy, you're keeping track of that counter. So there will be a parent of the incrementing function which is itself not a function because it keeps state. You could say your top level program is not a function because it keeps state.
Not neccessarily, when your program is (tail-)recursive you can carry the "current" value along without ever really mutating it. Haskell has the State monad which doesn't require any impurity.
> when your program is (tail-)recursive you can carry the "current" value along without ever really mutating it
right, what im curious though is, how one would go about making an app like say, itunes or the appstore in that way... it probably would go along way to help people understand these concepts
You can't. No useful program is stateless. Only examples and proofs-of-concept can be purely functional.
The lambda calculus is a way to define math in the functional style. Guess what? It needs state passed in to work. The names and orders of the integers must be passed in and held in a "state" in order to do anything useful. Since functional programming is centered around the concepts from the lambda calculus, this implies that all functional programs must have some "state" somewhere in order to start or do useful work.
If your program interacts with the outside world, then yes, it needs to be impure "along the edges" at least. But it can still keep track of state in a pure, functional way. Here's a simple example:
main :: IO ()
main = loop (0 :: Int) where
loop n = do
putStrLn $ "The counter is currently " <> show n <> ". Increase it by how much?"
increase <- readLn
loop $ n + increase
Here, the counter is updated purely, rather than by mutation.
Indeed, any useful program must have state and therefore cannot be entirely functional.
Only components or individual functions can be functional in style, the goal being to have as many of those as practical so that you don't touch state often and hopefully, only in a few places and using methods which set the state (rather than letting individual components "reach in" and set it themselves).
