generic image
Processing...
  • Games
  • Catalog
  • Develop
  • Robux
  • Search in Players
  • Search in Games
  • Search in Catalog
  • Search in Groups
  • Search in Library
  • Log In
  • Sign Up
  • Games
  • Catalog
  • Develop
  • Robux
   
ROBLOX Forum » Game Creation and Development » Scripters
Home Search
 

Re: Haskell: The Purely Functional Language

Previous Thread :: Next Thread 
TaslemGuy is not online. TaslemGuy
Joined: 10 Jun 2009
Total Posts: 12174
28 Sep 2012 09:46 PM
Here's some neat aspects of Haskell that make the language special, as well as their application to Lua.

(I deem this worthy of "advanced scripting discussion", but please correct me if I'm wrong).

Haskell is a purely functional language. This means functions dominate how you write code.

It also means a few more subtle things. Namely, you can't change the value of any variable.

But this is good! The "functional style" of programming is unusual but ends up being quite nice.

The typical example of functional programming is the definition of "factorial." Lua is semi-functional and thus can demonstrate both styles.

The typical definition (more or less, using while loops to emphasize clarity, not conciseness)

function factorial(n)
local s = 1
local i = 1
while i <= n do
s = s * i
i = i + 1
end
return s
end

It might seem impossible, at first, to define factorial without using any changing variables, but it's actually pretty easy.

function factorial(n)
if n == 0 then
return 1
else
return factorial(n-1) * n
end
end

No variables ever change here. So it's in the "functional style."

The equivalent code in Haskell is much more concise, because this is how all functions end up being defined.

factorial 0 = 1
factorial n = factorial (n-1) * n

You'll notice that functions here use concatenation to apply arguments. There's a relatively subtle reason for this which has to do with what is called "currying."

Before we delve into that, let's go for "lambda expressions." A lambda expression is essentially an anonymous function.

In Lua:
(function(x) return x + 1 end)(5) --> 6

In Haskell:
(\x -> x + 1) 5 --> 6

Since functions and lambda expressions are pretty important in Haskell, you can see pretty clearly that their syntax is pretty light, though maybe a bit peculiar.

Lambda expressions themselves are derived from the lambda calculus, which is a model of computation proven to be equivalent to Turing Machines (that is, it can perform any computation).

Lambda expressions in Haskell retain an interesting property: They can only take one argument.

But, then, functions are useless! You need to be able to take more than one argument! Actually, you don't!

Let's make a lambda expression that takes two arguments and returns their sum. But how? They can only take one! There's a solution!

(\x -> (\y -> x + y)) 4 5

Magic! What we have here is a function that takes a number and spits out a function that takes a number that spits out a sum.

The neat thing about this is that we have:

(\x -> (\y -> x + y)) 4 --> (\y -> 4 + y)

So you don't have to give ALL of the arguments to a function. You can give SOME of them and then pass that function along to do other stuff to it.

We can do this in Lua, too!

function sum(x)
return function(y) return x + y end
end

So I can say:

add_one = sum(1)
add_two = sum(2)

And then do:

add_one(5) --> 6
add_one(7) --> 8
add_two(9) --> 11
add_two(-1) --> 1

If I want to do both at the same time, I'd write:
sum(4)(5) --> 9

Since we don't want to be writing (\ -> (\ -> (\ -> ... over and over again, Haskell let's you just write multi-argument functions as such:

(\x y -> x + y)

Internally, it will rewrite it as

(\x -> (\y -> x + y))

This method of providing multiple arguments by returning functions from functions is called "Currying."

And it's super useful when it comes to using higher-order functions!

Let's go onto something else. Haskell is what's called "nonstrict."

Suppose you have the following code in Lua:

function forever()
while true do end
end

local t = { forever() , 5 }
t[2] --> infinite loop

We won't get our answer, because we've got to wait for t[1] to finish computing.

Not in Haskell!

Haskell is non-strict. Usually, this means Haskell is "lazy", but the standard doesn't require it.

More or less, this means Haskell will ignore a computation until it NEEDS it, so you can do the above without any kind of difficulty.

A more USEFUL aspect of the "laziness" is that you can create "infinite data structures."

Suppose I want an infinite list of 1's. In Lua, this isn't actually really possible, since you'd need infinite memory. But what if I only want a part of it at a time? Well, that could work. Haskell has the solution!

First, let's look at lists in Haskell. Since data can't change (no variables) arrays aren't useful. Instead there are lists. Specifically a linked cons list.

Here's a list: [1,4,2,7]

4 : [1,2,3] --> [4,1,2,3]

The : is "cons" or puts something at the beginning of a list.

Here's a simple list function: "take". {take n list} gives you the first 'n' elements in 'list.'

take 3 [6,2,8,3,1] --> [6,2,8]

Let's make an infinite list!

z = 1 : z

To see how that works, swap the 'z' on the right side with the whole right side, and repeat:

z --> 1 : z --> 1 : (1 : z) --> 1 : (1 : (1 : z)) --> ...

So I end up with [1,1,1,1,1,1,1,1,... and since Haskell is lazy, it doesn't care about the 1's after it sees them. So it can keep printing forever without running out of memory by ditching everything it no longer needs.

More usefully, I can say:

take 10 z --> [1,1,1,1,1,1,1,1,1,1]

Magic!

You can do more complex things, too:

q n = (n*n) : q (n+1)

Gives you: [1,4,9,16,25,36,49,64,81,100,121,144,169...

This is one feature of Haskell that is difficult to implement in Lua, because Lua is inherently strict and eager, with one exception: the and/or operators.

function cons(head,list)
local t = {}
t.head = head
t.tail = function() return list end
end

local z = {head = 1, tail = function() return z end}

function q(n)
return {head = n*n, tail = function() return q(n+1) end}
end

To get the first value, do list.head; To get the rest of the list, perform list.tail();

For instance:

function k()
local list = q(1)
local i = 0
while i < 15 do
i = i + 1
print(list.head)
list = list.tail()
end
end

Will print 1,4,9,16,25,36,49,64,81,100,121,144,169,196,225

Report Abuse
ArceusInator is not online. ArceusInator
Joined: 10 Oct 2009
Total Posts: 30553
28 Sep 2012 10:09 PM
This is moderately interesting.
Report Abuse
8SunTzu8 is not online. 8SunTzu8
Joined: 30 Sep 2011
Total Posts: 8199
28 Sep 2012 10:31 PM
I think I stopped a quarter of the way through...

But I do agree, it was interesting. There are some really unique types of programming languages out there...

"Contact me if you are interested in becoming a developer, innovator, or recruiter for CSA."
Report Abuse
BlueTaslem is not online. BlueTaslem
Joined: 11 May 2008
Total Posts: 11060
28 Sep 2012 10:37 PM
It is in many ways 'better' except that it does not either model a turing machine more directly or model a von neumann machine more directly than traditional imperative programming.
Report Abuse
Davidii is not online. Davidii
Joined: 17 Jul 2008
Total Posts: 1282
29 Sep 2012 07:53 AM
Tl;dr

I'm typically apathetic to languages I don't know.
Report Abuse
Quenty is not online. Quenty
Joined: 03 Sep 2009
Total Posts: 9316
29 Sep 2012 08:06 AM
Besides being good for speed coding, what else is it really good at? Does it handle large datasets well?
Report Abuse
SN0X is not online. SN0X
Joined: 24 Oct 2011
Total Posts: 7277
29 Sep 2012 08:42 AM
"I think I stopped a quarter of the way through... "

As did I.

But there were some interesting concepts there.

I think I'll try Haskell. Don't know when though; I'm pretty busy.
Report Abuse
TaslemGuy is not online. TaslemGuy
Joined: 10 Jun 2009
Total Posts: 12174
29 Sep 2012 11:57 AM
@Quenty

Haskell is more concise, easier to read, and much shorter than typical imperative code.

It also has a tendency when done right to be high modular and composable.

Due to the typing system, which I skipped over, it's also easier to write correct code.

It's also easy to prove correctness of Haskell programs, which makes it applicable to mathematics.

It has pretty good parsing libraries and excellent symbolic manipulation.

It has extensive and useful testing libraries and profiling.

When it's used correctly it can be fast, comparable to, say, C.

For instance, Quicksort in Haskell:

quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs

The type system lets you verify that it should work, and it runs really fast.

Also, Haskell supports out-of-the-box unlimited precision Integers, which is awesome.

It also teaches design strategies. For instance, tail-call recursion for improved speed (I don't think this quite works in Lua, though like the other examples I can think of ways to implement it indirectly)

fac' 0 a = a
fac' x a = fac' (x-1) (a*x)
fac x = fac' x 1

Which won't stackoverflow no matter how deeply it's called. When interpreted and not compiled, fac 300 runs in under a tenth of a second.

306057512216440636035370461297268629388588804173576999416776741259476533176716867465515291422477573349939147888701726368864263907759003154226842927906974559841225476930271954604008012215776252176854255965356903506788725264321896264299365204576448830388909753943489625436053225980776521270822437639449120128678675368305712293681943649956460498166450227716500185176546469340112226034729724066333258583506870150169794168850353752137554910289126407157154830282284937952636580145235233156936482233436799254594095276820608062232812387383880817049600000000000000000000000000000000000000000000000000000000000000000000000000
Report Abuse
SN0X is not online. SN0X
Joined: 24 Oct 2011
Total Posts: 7277
29 Sep 2012 12:36 PM
"Also, Haskell supports out-of-the-box unlimited precision Integers, which is awesome."

"which is awesome"

Agreed.

Can't wait to try it out.

Fibonacci should be exciting :D
Report Abuse
TaslemGuy is not online. TaslemGuy
Joined: 10 Jun 2009
Total Posts: 12174
29 Sep 2012 02:13 PM
@SN0X

Here's a hint for Fibonacci: The naive implementation is very bad.

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

It's not immediately obvious what's wrong with this. The problem is that every call with recursively call two more, giving time complexity O(2^n). This means that while you can reasonably calculate the first 10, good luck getting the 100th.

The main reason it's slow is because you're recomputing when you don't need to. Remember the solution to a previous calculation is called "memoization" and it's an important efficiency/optimization tool.

The typical way to memoize the above algorithm is to create a list of values:

fib' 0 = 0
fib' 1 = 1
fib' n = fibs !! (n-1) + fibs !! (n-2)

fibs = map fib' [0..]

fib n = fibs !! n

Which will be very, very fast.

On notation:

[0..] is the list of numbers [0,1,2,3,4,5,6,...] demonstrating both lazy lists and arbitrary precision integers.

map is a function that "maps" a function over a list. In this case, we're calling fib' for each number in the list [0..], so it ends up being [fib' 0, fib' 1,fib' 2, fib' 3,...]

Also note that using ' is permitted in variable names under certain circumstances, such as at the end.

The above implementation of fib is also not tail-recursive, which can be problematic.
Report Abuse
BlueTaslem is not online. BlueTaslem
Joined: 11 May 2008
Total Posts: 11060
29 Sep 2012 02:24 PM
Your last bit about lazy evaluation is indeed possible with Lua, but not by using normal tables. Essentially, that's what metatables are for.
Report Abuse
SN0X is not online. SN0X
Joined: 24 Oct 2011
Total Posts: 7277
30 Sep 2012 02:21 AM
I tried Haskell out yesterday.

Heck, what is that syntax.

It confuses me.
Report Abuse
trappingnoobs is not online. trappingnoobs
Joined: 05 Oct 2008
Total Posts: 19100
30 Sep 2012 05:24 AM
"It confuses me."

"yesterday"
there is your answer
Report Abuse
TheMyrco is not online. TheMyrco
Joined: 13 Aug 2011
Total Posts: 15105
30 Sep 2012 09:24 AM
What would happen if you'd combine Lua with Haskell, lolz =D
Report Abuse
SN0X is not online. SN0X
Joined: 24 Oct 2011
Total Posts: 7277
30 Sep 2012 09:36 AM
a metatabled function would come out
Report Abuse
TheMyrco is not online. TheMyrco
Joined: 13 Aug 2011
Total Posts: 15105
30 Sep 2012 10:11 AM
Challenge accepted. =D
Report Abuse
TaslemGuy is not online. TaslemGuy
Joined: 10 Jun 2009
Total Posts: 12174
30 Sep 2012 10:56 AM
I don't think there's a healthy mix.

Lua is imperative with functional features while Haskell is purely functional.

Report Abuse
Previous Thread :: Next Thread 
Page 1 of 1
 
 
ROBLOX Forum » Game Creation and Development » Scripters
   
 
   
  • About Us
  • Jobs
  • Blog
  • Parents
  • Help
  • Terms
  • Privacy

©2017 Roblox Corporation. Roblox, the Roblox logo, Robux, Bloxy, and Powering Imagination are among our registered and unregistered trademarks in the U.S. and other countries.



Progress
Starting Roblox...
Connecting to Players...
R R

Roblox is now loading. Get ready to play!

R R

You're moments away from getting into the game!

Click here for help

Check Remember my choice and click Launch Application in the dialog box above to join games faster in the future!

Gameplay sponsored by:
Loading 0% - Starting game...
Get more with Builders Club! Join Builders Club
Choose Your Avatar
I have an account
generic image