Thinking in functional programming

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
levicc00123
Posts: 165
Joined: Thu Jan 03, 2008 5:33 pm UTC
Location: Sterling, CO
Contact:

Thinking in functional programming

Postby levicc00123 » Mon Apr 11, 2011 5:07 pm UTC

I'm working on a project in haskell, and the main brick wall that I keep hitting my head against is that I'm trying to code in an imperative style, which you can't do, and it's making me mad, does anyone have any advice for a fellow seeker of wisdom?
Image

User avatar
b.i.o
Green is the loneliest number
Posts: 2519
Joined: Fri Jul 27, 2007 4:38 pm UTC
Location: Hong Kong

Re: Thinking in functional programming

Postby b.i.o » Mon Apr 11, 2011 6:50 pm UTC

levicc00123 wrote:I'm working on a project in haskell, and the main brick wall that I keep hitting my head against is that I'm trying to code in an imperative style, which you can't do, and it's making me mad, does anyone have any advice for a fellow seeker of wisdom?

There are two things that got me really thinking functionally. The first was the book The Little Schemer. Scheme is a very different functional language than Haskell, but reading this for the first time was the first time I really got recursion.

The other thing that's helped me a lot is my use of functional features in other languages. Two big examples are list comprehensions and first-class functions. I use both constantly, even in languages that aren't completely functional (like Python), and that means that when I am using a completely functional language, my programming style doesn't actually change all that much.

Mainly though it's just practice. When I was learning Haskell for the first time I was reading 3-4 different books/tutorials on it simultaneously, and Haskell wasn't my first functional language.

User avatar
headprogrammingczar
Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: Thinking in functional programming

Postby headprogrammingczar » Mon Apr 11, 2011 9:47 pm UTC

Lots of practice. Get in the habit of writing 10 3-line functions instead of one thirty-line function. Get in the habit of thinking about what things ARE, not what they DO. Mostly though, a lot of practice. It's really the best way to break any habit.
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you

User avatar
MHD
Posts: 630
Joined: Fri Mar 20, 2009 8:21 pm UTC
Location: Denmark

Re: Thinking in functional programming

Postby MHD » Wed Apr 13, 2011 7:24 am UTC

As has been said, break up your code into small functions.

And list comprehensions are a good beginners tool.
EvanED wrote:be aware that when most people say "regular expression" they really mean "something that is almost, but not quite, entirely unlike a regular expression"

lgw
Posts: 437
Joined: Mon Apr 12, 2010 10:52 pm UTC

Re: Thinking in functional programming

Postby lgw » Wed Apr 13, 2011 7:26 pm UTC

Seconding The Little Schemer - reading The Little Lisper back in the day solved this exact problem for me. It's short and the problems are OK - some are fun.
"In no set of physics laws do you get two cats." - doogly

User avatar
levicc00123
Posts: 165
Joined: Thu Jan 03, 2008 5:33 pm UTC
Location: Sterling, CO
Contact:

Re: Thinking in functional programming

Postby levicc00123 » Fri Apr 15, 2011 10:45 am UTC

Thanks everyone for your suggestions, I've got a copy of the little schemer ordered and on it's way.
Image

User avatar
b.i.o
Green is the loneliest number
Posts: 2519
Joined: Fri Jul 27, 2007 4:38 pm UTC
Location: Hong Kong

Re: Thinking in functional programming

Postby b.i.o » Fri Apr 15, 2011 1:58 pm UTC

When you get it, I recommend Racket (formerly PLT Scheme) for working through it. It's really easy to get set up and has a mini-IDE included (with a REPL and helpful things like step-through debugging).

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Thinking in functional programming

Postby WarDaft » Fri Apr 15, 2011 5:31 pm UTC

The main difference is that in imperative programming, you're always saying "and then I want..."

In functional programming, you're just saying "I want..."



For practice, try writing a function that depends in part on the return value of the next function it calls to determine some of the parameters it will call that very function with.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Anubis
Posts: 222
Joined: Sun Mar 01, 2009 7:59 am UTC

Re: Thinking in functional programming

Postby Anubis » Sat Apr 16, 2011 7:59 am UTC

WarDaft wrote:For practice, try writing a function that depends in part on the return value of the next function it calls to determine some of the parameters it will call that very function with.


Are you intentionally trying to confuse the OP? Because either you've misstated the problem or you're asking for the impossible.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Thinking in functional programming

Postby Berengal » Sat Apr 16, 2011 8:25 am UTC

Anubis wrote:
WarDaft wrote:For practice, try writing a function that depends in part on the return value of the next function it calls to determine some of the parameters it will call that very function with.


Are you intentionally trying to confuse the OP? Because either you've misstated the problem or you're asking for the impossible.
No no, quite possible, quite sane.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Thinking in functional programming

Postby WarDaft » Sat Apr 16, 2011 4:11 pm UTC

And excellent practice for getting into the Haskell mindset.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Anubis
Posts: 222
Joined: Sun Mar 01, 2009 7:59 am UTC

Re: Thinking in functional programming

Postby Anubis » Sat Apr 16, 2011 7:03 pm UTC

Could you provide an example of what you are asking for? Because calling a function with parameters that depend on the return value of that call is analogous to writing the logical statement "The truth value of this statement is the opposite of the truth value that this statement evaluates to", so it should be quite interesting to see such a call.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Thinking in functional programming

Postby Berengal » Sat Apr 16, 2011 8:20 pm UTC

Aha! I was waiting for just that question, and have indeed prepared an example!

The problem we'll tackle is quite a silly one: Parsing of a simple data stream format defined as such:
  • The character "e" not followed by anything (indicating the end)
  • A single digit number not zero (encoded in ascii) followed by that number of characters of data, followed by the rest of the data
  • A zero, followed by a single digit number not zero, followed by a decimal number containing the previous number of digits, followed by the last number of characters of data, followed by the rest of the data

Some examples are:
  • "11e" meaning the character "1"
  • "3fooe" meaning the string "foo"
  • "2hi5helloe" meaning the string "hi" and the string "hello"
  • "0213Hello, world!e" meaning the string "Hello, world!"
  • "e" meaning empty (no data)

(Note that the empty string isn't valid).

We want to tokenize strings on this format, turning them into something that's a bit easier to program with. We define a token to be this:

Code: Select all

data Token = TokenLength Int -- A token indicating the length of the next token
           | Data String -- The data itself
           | End -- The end marker
           deriving (Show)

For clarity we also define this type alias:

Code: Select all

type Lexeme = String

Now we can easily write a tokenizer; a function turning a list of lexemes into a list of tokens. We do that like this:

Code: Select all

tokenize :: [Lexeme] -> [Token]
tokenize (x:xs) = case x of
  "e" -> [End] -- The lexeme "e" means the token End and the end of the data stream
  "0" -> -- The lexeme "0" means a TokenLength of 1, and determines that the next lexeme is itself a TokenLength token which contains the length of the lexeme (which is itself a TokenLength token, but we don't need to worry about that here. We just recurse on the rest of the stream).
    let (x' : xs') = xs
    in TokenLength 1 : TokenLength (read x') : tokenize xs'
  x | all isNumber x -> -- The lexeme containing only digits means a TokenLength token of the parsed number, and the next lexeme is a Data token. The stream may have more tokens, so we recurse on it.
    let (x' : xs') = xs
    in TokenLength (read x) : Data x' : tokenize xs'

This should be pretty straightforward if you're familiar with Haskell syntax already. If not, a (probably too) short introduction to the relevant bits:
  • ":" is a list-building operator. It takes an element of the left, a list on the right and returns a the list with the element in front. "1 : [2,3] -> [1,2,3]"
  • Names to the left of an "=" (or "->" in "case of" expressions) binds variables. "x = 5" makes x the name of the value 5.
  • Patterns can also appear on the left of "=" (and "->"). A pattern looks inside the value on the right, and if the structure matches, variables are bound to the corresponding value. "(x : xs) = 1 : (2 : (3 : []))" would make x the name for 1 and xs the name for [2,3]
  • Oh, and "[1,2,3]" is just syntactic sugar for "1 : 2 : 3 : []", and since ":" is right-associative that means the same as "1 : (2 : (3 : []))". "[]" is the empty list.
  • Patterns can themselves contain patterns, so you can dig deep into structures in a single pattern.
  • Patterns fail if the structure doesn't match. When that's the case, the next pattern is tried. If all patterns fail there is an error and your program fails.
  • Patterns may have guards attached. "foo | bar = baz" means the same as "foo = baz", except "bar" must be true for the match to succeed.
Okay, so a bit of syntax out of the way. Hopefully the rest of the syntax will make sense in context (syntax highlighting might help).

So we have a tokenizer. This should work, and we can test it:

Code: Select all

*Main> tokenize ["3", "foo", "e"]
[TokenLength 3,Data "foo",End]
*Main> tokenize ["0", "2", "13", "Hello, world!", "e"]
[TokenLength 1,TokenLength 2,TokenLength 13,Data "Hello, world!",End]

Everything seems to be working just fine.

We need to lex the string however; chop it up into little bits suitable for consumption by our tokenizer. Lexers often just break up the input string on whitespace or word boundaries or some other trivial bits easily extracted from the input string itself, but ours need an extra bit information: A list of lexeme lengths. We write it like this:

Code: Select all

lexInput :: String -> [Int] -> [Lexeme]
lexInput "" _ = [] -- The empty string means we've reached the end of the input, so just return the empty list. Note that it's not really valid to call this with an empty string since that's not defined in the grammar, but since we're recursing here we get the empty string when we reach the end.
lexInput s (n:ns) = let (lexeme, rest) = splitAt n s -- Just split the string after the first n characters...
                    in lexeme : lexInput rest ns -- ... then recurse on the rest (putting the lexeme found first in the output stream)

All well and good. Anyone who knows how to code a little bit, and Haskell syntax, could write this. Simples. Let's test it:

Code: Select all

*Main> lexInput "3fooe" [1, 3, 1]
["3","foo","e"]
*Main> lexInput "215e" [1, 2, 1]
["2","15","e"]

We can also test the lexer and the tokenizer together:

Code: Select all

tokenize (lexInput "3fooe" [1,3,1])
[TokenLength 3,Data "foo",End]

Works just fine. Except now we need to make that list of lexeme lengths somehow.

The easy way of doing this is to just go through the token stream; it already contains the lengths of the lexemes. The function therefore looks like this:

Code: Select all

lexemeLengths :: [Token] -> [Int]
lexemeLengths tokens = 1 : lengths tokens -- The first lexeme always has length 1. The rest depends on the tokens themselves
  where lengths (TokenLength n : rest) = n : lengths rest -- A TokenLength token means the next lexeme has the length indicated in the token
        lengths (Data _ : rest) = 1 : lengths rest -- A Data token means the lexeme after it has length 1
        lengths [End] = [] -- An End token means there are no more lexemes after it. The lengths of those are obviously the empty list of lengths.

And for good measure, let's test that one as well:

Code: Select all

*Main> lexemeLengths [End]
[1]
*Main> lexemeLengths [TokenLength 3, Data "foo", End]
[1,3,1]

Like all the others, this one works fine too. Now we just need to plug all the right inputs and outputs together in the parser:

Code: Select all

parse :: String -> [Token]
parse string = let lexemes = lexInput string lengths -- The lexemes are the output of the lexInput function applied to the input string and the lexeme lengths list
                   lengths = lexemeLengths tokens -- The lexeme lengths list is the output of the lexemeLengths function applied to the token list
                   tokens = tokenize lexemes -- The token list is the output of the tokenize function applied to the list of lexemes.
               in tokens -- We want the tokens, so return those.

How does this work? It works just fine:

Code: Select all

*Main> parse "3fooe"
[TokenLength 3,Data "foo",End]
*Main> parse "0213Hello, world!e"
[TokenLength 1,TokenLength 2,TokenLength 13,Data "Hello, world!",End]

The Aristocrats!
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
Anubis
Posts: 222
Joined: Sun Mar 01, 2009 7:59 am UTC

Re: Thinking in functional programming

Postby Anubis » Sat Apr 16, 2011 9:34 pm UTC

That's all well and good, but can you please point out precisely which part of that example involves "a function that depends in part on the return value of the next function it calls to determine some of the parameters it will call that very function with"?

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Thinking in functional programming

Postby EvanED » Sat Apr 16, 2011 10:30 pm UTC

Anubis wrote:That's all well and good, but can you please point out precisely which part of that example involves "a function that depends in part on the return value of the next function it calls to determine some of the parameters it will call that very function with"?

If you look at the last bit, you'll see an interesting circularity: lexInput takes lengths as a parameter and returns lexemes; tokenize takes lexemes and returns tokens; lexemeLengths takes tokens and returns lengths, and we're back to the beginning.

It's interesting, while I'd have to look at it more to fully understand the connection, my gut feeling is that it's achieving something like mutual recursion via lazy evaluation.

(Also, you're using "tokenizer" in a pretty non-standard way. But that's besides the point. ;-))

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Thinking in functional programming

Postby WarDaft » Sun Apr 17, 2011 4:34 am UTC

Anubis wrote:That's all well and good, but can you please point out precisely which part of that example involves "a function that depends in part on the return value of the next function it calls to determine some of the parameters it will call that very function with"?


Okay, here's a more concise example. Not as clever mind you. Perhaps slightly more transparent in why it can work.

A slightly more complicated than necessary method to move all capital Cs one character earlier in a string.

Code: Select all

switcher [] = []
switcher (x:xs) = p $ switcher ns
  where
    (p, c) = if a then (id, Just x) else ((x:), Nothing)
    (a, ns) = switcher' xs c
    switcher' [] = (,) False . (\x -> [])
    switcher' (y:ys) = (,) (y=='C') . swap
      where
        swap (Just s) = y:s:ys
        swap Nothing = y:ys


And yes, it works.

Code: Select all

*Main> switcher "abCdeCCf"
"aCbdCCef"
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Anubis
Posts: 222
Joined: Sun Mar 01, 2009 7:59 am UTC

Re: Thinking in functional programming

Postby Anubis » Sun Apr 17, 2011 5:34 am UTC

I still don't see any function calls taking their own return value as a parameter. I see what you're trying to do, but it's not at all what you originally asked for. Which is why I suggested that perhaps you had misstated it.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Thinking in functional programming

Postby WarDaft » Sun Apr 17, 2011 5:43 am UTC

Anubis wrote:I still don't see any function calls taking their own return value as a parameter. I see what you're trying to do, but it's not at all what you originally asked for. Which is why I suggested that perhaps you had misstated it.


No, that's exactly what I said. A function that depends, in part, on the return value of the next function it calls, to determine some of the parameters it will call that very function with.

The value c takes when passed to switcher' xs is determined by the value of a, which depends on what switcher' xs c returns. That's exactly what I promised.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
thoughtfully
Posts: 2253
Joined: Thu Nov 01, 2007 12:25 am UTC
Location: Minneapolis, MN
Contact:

Re: Thinking in functional programming

Postby thoughtfully » Sun Apr 17, 2011 5:46 am UTC

It sounds more like declarative programming (Prolog/Makefiles/SQL SELECT) than functional to me.

Or maybe it's an unholy mootant hybrid! I get that vibe from Haskell sometimes :)
In a good way!
Image
Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.
-- Antoine de Saint-Exupery

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Thinking in functional programming

Postby Berengal » Sun Apr 17, 2011 5:53 am UTC

How about these standard combinators?

Code: Select all

fix :: (a -> a) -> a
fix f = let x = f x in x

loop :: ((a, b) -> (c, b)) -> a -> c
loop f input = let (output, feedback) = f (input, feedback) in output


Edit: Made some dataflow diagrams, since I find that more educational than code in these cases:
dataflow.png
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
headprogrammingczar
Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: Thinking in functional programming

Postby headprogrammingczar » Sun Apr 17, 2011 1:06 pm UTC

Another example, except I will actually walk you through how it works. :P

Code: Select all

fibs = 1:1:(zipWith (+) fibs (tail fibs))


Remember lazy evaluation keeps this from exploding right away. So say we want to look at the first element. We see a one.

Code: Select all

fibs = 1:(SOMETHING)


We look again and see another one.

Code: Select all

fibs = 1:1:(SOMETHING)


Now when we look again, we are actually picking the first value out of the zipWith expression.

Code: Select all

zipWith f (x:xs) (y:ys) = (f x y):(zipWith f xs ys)


So to get that value, we need the head of the first parameter, fibs. Oh look! We already know it is a one! We also need the head of the second parameter, which is (tail fibs). The first element of the tail is the second element, which is also a one. We add them together and get two.

Code: Select all

fibs = 1:1:2:(SOMETHING)


Now we look again, which is our second pattern match against zipWith. Now instead of looking at the first and second elements of fibs, we are looking at the second and third. The second element we already know is a one, and we just computed the third element which is a two. Add them and get three.

Code: Select all

fibs = 1:1:2:3:(SOMETHING)


We can continue like this forever, giving us an infinite lazy list of Fibonacci numbers.
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you

User avatar
Anubis
Posts: 222
Joined: Sun Mar 01, 2009 7:59 am UTC

Re: Thinking in functional programming

Postby Anubis » Sun Apr 17, 2011 9:12 pm UTC

These are all just examples of recursion. I think we're obviously interpreting the original request in fundamentally different ways. You're showing me functions with their return value passed as a parameter to the next call of that function, whereas the way the original request is written it sounds like its asking for a function call with its return value passed as a parameter to the very same call, which could obviously never be evaluated (in fact, I don't think such a call could even be written).

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Thinking in functional programming

Postby WarDaft » Mon Apr 18, 2011 2:20 am UTC

Anubis wrote:These are all just examples of recursion. I think we're obviously interpreting the original request in fundamentally different ways. You're showing me functions with their return value passed as a parameter to the next call of that function, whereas the way the original request is written it sounds like its asking for a function call with its return value passed as a parameter to the very same call, which could obviously never be evaluated (in fact, I don't think such a call could even be written).


Thats what we offered. In Haskell, (well, in the code offered) you can set the value of variables 'after' you use them.

Code: Select all

fn a = r
  where
    r = b `mod` b
    b = 2 - c
    c = a * a
...is perfectly valid, and the return value will be (2 - a*a) mod a.


Likewise...

Code: Select all

a = 1 : b
b = 2 : a
...results in a being [1,2,1,2,1,2...] and b being [2,1,2,1,2,1...].

This is because that these definitions are all simultaneous - the compiler is not interpreting them as "Okay, first I set r to this, then b to that, then c to that", it's interpreting them as "r, b, and c have these relations, I need b for r, and c for b... okay then."

So, when I wrote:

Code: Select all

    (p, c) = if a then (id, Just x) else ((x:), Nothing)
    (a, ns) = switcher' xs c
The "a" used in the if is defined on the second line - because these are not sequential definitions, but simultaneous ones.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Thinking in functional programming

Postby Berengal » Mon Apr 18, 2011 5:33 am UTC

Anubis wrote:These are all just examples of recursion. I think we're obviously interpreting the original request in fundamentally different ways. You're showing me functions with their return value passed as a parameter to the next call of that function, whereas the way the original request is written it sounds like its asking for a function call with its return value passed as a parameter to the very same call, which could obviously never be evaluated (in fact, I don't think such a call could even be written).
Take another look:
Berengal wrote:

Code: Select all

fix :: (a -> a) -> a
fix f = let x = f x in x
Where is the recursion?
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

Outchanter
Posts: 669
Joined: Mon Dec 17, 2007 8:40 am UTC

Re: Thinking in functional programming

Postby Outchanter » Mon Apr 18, 2011 9:14 pm UTC

Anubis: the point is that making a "function call" is in Haskell is an altogether more flexible concept than doing so in an imperative language.

For example, if you have functions (of single variables) f and g, you could combine them into a function that does both. In Python it could look like this:

Code: Select all

def f_and_g(x, y):
   return f(x), g(y)


Now using only f_and_g, you wouldn't be able to call f without calling g or vice versa. So if you did this:

Code: Select all

def f(x):
   return x + 2
def g(y):
   return g(y) # infinite loop


You would be in trouble calling f_and_g even if you only wanted the result from f. However in Haskell, due to lazy evaluation, there is no such problem:

Code: Select all

f x = x + 2
g y = g y
f_and_g x y = (f x, g y)
(a, b) = f_and_g 1 2

main = putStrLn (show a)
-- outputs 3


So in Haskell, thanks to the magic of lazy evaluation, what looks like one function call can behave like two completely independent function calls. Once you realize this, it's trivial to take a return value from g and pass it as a parameter to f, which in the scheme of f_and_g is "using a return value as a parameter to the same function call":

Code: Select all

f x = x + 2
g y = y * 3
f_and_g x y = (f x, g y)
(a, b) = f_and_g b 1 -- MAGIC HAPPENS HERE

main = putStrLn (show a)
-- outputs 5


The "magic happens here" line is no different to

Code: Select all

b = g 1
a = f b


The difference is that in an imperative language, a function is a chunk of code, which is either executed fully or isn't executed at all. But in a lazy functional language, a function is more like a dependency graph describing how you would calculate any of the returned values, when and if you needed them. If there are multiple returned values, they don't necessarily have to be computed at the same time.

Uncompetative
Posts: 3
Joined: Sun Jun 13, 2010 4:52 pm UTC

Re: Thinking in functional programming

Postby Uncompetative » Sat Apr 23, 2011 11:58 am UTC

levicc00123 wrote:I'm working on a project in haskell, and the main brick wall that I keep hitting my head against is that I'm trying to code in an imperative style, which you can't do, and it's making me mad, does anyone have any advice for a fellow seeker of wisdom?

You can program in an imperative style, you just put that code in a 'do'.

However, Haskell programmers are encouraged to make the majority of their programs purely functional. That is:

- NOT functions as they are in C (which are really mis-named procedures as they allow you to destructively update global variables), whereas a pure function can only set the values of variables passed into it as arguments
- NOT variables as they are in C (which are really mis-named "cells", think Spreadsheet cells, which support destructive update operations like assignment), but which are like the variables of classical mathematics:

A variable is an undefined symbol which returns that textual name until such time that it is defined through an attachment to a typed software entity, such as a literal constant number value. It may NOT be redefined.

So, rather than reuse temporary "cells" for different subtotals of a calculation in your program, you would be forced to give each occurrence a new name.

This explains the use of recursion (as opposed to for/next loops), as the function being re-invoked can seemingly re-use the same set of names for its calculation. However, it can only do this because a function invocation (even to itself from within the body of its own function definition), gets you a fresh "lexical scope" where the only defined names are those of the parameters explicitly captured by dint of position (and matching type patterns in some languages), locally defined names and anonymous inline functions (which is what a lambda function is) and any (global) library functions that your own definitions haven't "occluded" from view. THIS IS COMPLICATED. However, the best way to understand it is to look at how the language makes use of its Stack - or just try to grasp Forth. I suppose, C lets you manage your own memory and data transfers, whilst Haskell, etc. does all of this for you and cleans up the garbage afterwards.

Pipelining information through nested / chained functions is all fine and dandy until you hit an exception or need to do some I/O. If a function y = f(x) is thought of as an arrow mapping x to y as in: x -f-> y then you would need to put the exception generated by that function, or its side-effecting I/O actions in a kind of wrapper making this "monad" (for that it what I am attempting to describe), look more like: x =f=> y where the second line suggests the wrapped thingy.

Well, here's hoping Berengal doesn't tear this to shreds.

;-)

User avatar
Meteorswarm
Posts: 979
Joined: Sun Dec 27, 2009 12:28 am UTC
Location: Ithaca, NY

Re: Thinking in functional programming

Postby Meteorswarm » Sun Apr 24, 2011 4:58 pm UTC

Uncompetative wrote:Pipelining information through nested / chained functions is all fine and dandy until you hit an exception or need to do some I/O. If a function y = f(x) is thought of as an arrow mapping x to y as in: x -f-> y then you would need to put the exception generated by that function, or its side-effecting I/O actions in a kind of wrapper making this "monad" (for that it what I am attempting to describe), look more like: x =f=> y where the second line suggests the wrapped thingy.

Well, here's hoping Berengal doesn't tear this to shreds.

;-)


IO in Haskell is done through monads, but, because it's lazy, your (purely functional) code can on-demand read from a file.

If I had some code that read lines from the file, and counted the number more than 80 characters, it wouldn't actually read from the file when I "assign" the string of its contents to a variable - that would only happen when the values were forced, probably by a print call after the analysis phase.

I actually had a little trouble with this when I, like a good programmer, closed my filehandle immediately after assigning its contents to a string, and then my program thought the string was empty because when it went to look for the contents, they weren't there.

Closing after forcing the values solves that problem. Normally, you force when you print output or something, but you can also force stuff at other times if you want to - for example, not wanting to have a ton of open files floating around.
The same as the old Meteorswarm, now with fewer posts!

Uncompetative
Posts: 3
Joined: Sun Jun 13, 2010 4:52 pm UTC

Re: Thinking in functional programming

Postby Uncompetative » Tue Apr 26, 2011 11:56 am UTC

Meteorswarm wrote:
Uncompetative wrote:Pipelining information through nested / chained functions is all fine and dandy until you hit an exception or need to do some I/O. If a function y = f(x) is thought of as an arrow mapping x to y as in: x -f-> y then you would need to put the exception generated by that function, or its side-effecting I/O actions in a kind of wrapper making this "monad" (for that it what I am attempting to describe), look more like: x =f=> y where the second line suggests the wrapped thingy.

Well, here's hoping Berengal doesn't tear this to shreds.

;-)


IO in Haskell is done through monads, but, because it's lazy, your (purely functional) code can on-demand read from a file.

If I had some code that read lines from the file, and counted the number more than 80 characters, it wouldn't actually read from the file when I "assign" the string of its contents to a variable - that would only happen when the values were forced, probably by a print call after the analysis phase.

I actually had a little trouble with this when I, like a good programmer, closed my filehandle immediately after assigning its contents to a string, and then my program thought the string was empty because when it went to look for the contents, they weren't there.

Closing after forcing the values solves that problem. Normally, you force when you print output or something, but you can also force stuff at other times if you want to - for example, not wanting to have a ton of open files floating around.

Yes, but because Haskell does so much for you "behind the scenes" at weird times of its own choosing it is hard to intuitively gauge that your algorithm isn't needlessly inefficient due to this. As a result I have to admit that I am skeptical of full-blown pure functional programming languages, but feel that they make a nice complement to other paradigms. So, starting closest to the GPU then moving through multiple multi-threaded multi-core CPUs to a fast LAN providing distributed computational resources you'd mix Array Programming (e.g. APL, R), Functional Programming (e.g. Haskell, Fortress) and Concurrency-Oriented Programming (e.g. Erlang) - where the less efficient language is used to handle the higher latency hardware.

This is not intended as an inflammatory attack on Haskell, by any means. It is just an observation of mine that any language that comes on the scene with some fashionable concept tends to over use it almost in some desperate attempt to prove that the concept must be worthwhile because "you can do everything with it". I've seen this again and again; with everything being an object in Smalltalk, or Lua only having tables, or LISP's infatuation with lists.

Sure, it does make for a simpler language semantics which may prove more flexible as a result of its uniformity, but I feel that this comes at the cost of articulacy, readability and efficiency- due to the tyranny of this monoparadigm shaping the way you think and limiting the precision of your coherent expression.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Thinking in functional programming

Postby Berengal » Tue Apr 26, 2011 4:22 pm UTC

Lazy IO is not recommended. It's there for writing quick filters in a language somewhat more structured than bash, not something you're supposed to use in programs longer than 30 lines.

If you think that because Haskell is lazy then IO in haskell is lazy has completely missed the distinction between evaluation and execution and the entire reason why execution commands are all in the IO type constructor.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 11 guests