View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

8 replies to this topic

Posted 24 January 2013 - 03:20 PM

So I'm trying to learn Haskell with an extremely simple lfsr program.  I've have working code and I've got a decent understanding thanks to the first half of Learn You a Haskell for Great Good, but I'd like to apply some of what I've learned before I go too much further.  I keep tweaking this code and getting all kinds of cryptic errors, but I think I've got it close.  If anyone can help me understand what's gone wrong, that would be awesome.

This throws an error complaining about "infinite type" occurring in post.  I think it thinks I'm trying to be recursive or something.  Any thoughts?

{- Random Number Generator -}

import Data.Bits

| (seed .&. 1) == 1 = post
| otherwise         = post xor mask
where post = (seed shift (-1))

### #2stevenmarky  Members

Posted 24 January 2013 - 04:51 PM

The problem is "post xor mask" on line 7.

It should be "xor post mask" because the function comes first (unless it's an infix operator).

You can still use it as infix with special syntax:

"post xor mask"

Posted 24 January 2013 - 06:40 PM

Ah yes, thank you.  How foolish of me.  See, this is why I don't like inconsistency.
Thanks again, Steven.

### #4Geometrian  Members

Posted 25 January 2013 - 10:20 AM

See, this is why I don't like inconsistency.

Try Scheme or some other Lisp then.

Edited by Geometrian, 25 January 2013 - 10:20 AM.

And a Unix user said rm -rf *.* and all was null and void...|There's no place like 127.0.0.1|The Application "Programmer" has unexpectedly quit. An error of type A.M. has occurred.

Posted 25 January 2013 - 05:15 PM

Try Scheme or some other Lisp then.

lmao! that's great.

i like haskell, at least I think I do lol.

### #6Geometrian  Members

Posted 25 January 2013 - 07:56 PM

Actually, just to clarify, I mean that in all seriousness.

Having used both languages, I will say that Haskell's power is amazing. Its type inference is one step shy of spooky, and pattern matching is pretty much overloading for functional languages. It's fast, it's slick, and can be terse when you want it. There are no privileged types--you write your own custom type, and it's a first-class object same as anything. If it didn't sound so ridiculous, I'd say that these user types make Haskell an at least semi-object-oriented language.

That said, I don't use Haskell since its syntax is overcomplicated. I respect its power, but there's more than one way to do something, and remembering exactly how something happens really hurts. In imperative languages, I'd compare Haskell to C++. Both are really really powerful, but learning the language requires accommodating inconsistency. I hate doing that.

By contrast, Scheme is a simple language. It's a bit slow, and maybe more verbose to use, but it turns the words "letrec", "define", and the humble parenthesis into a Turing-complete language of expressive power at least on par with Haskell. In imperative languages, who can boast of lexical closures? In Scheme, just the order of something intuitively and beautifully defines the most complex ideas you can create. It's not the most hip language, but it is by far in my mind superior to Haskell.

Put simply, Scheme is beautiful. There is something gorgeous about the purest expression of something. For the functional programming style, Scheme is it.

And a Unix user said rm -rf *.* and all was null and void...|There's no place like 127.0.0.1|The Application "Programmer" has unexpectedly quit. An error of type A.M. has occurred.

### #7swiftcoder  Senior Moderators

Posted 26 January 2013 - 01:31 AM

In imperative languages, who can boast of lexical closures?

Doesn't pretty much every modern imperative language has some form of closures (i.e. C++11's lambda)?

In addition, objects (in an OOP sense) contain state which they bind to functions - that makes them isomorphic with respect to closures. i.e. constructs like Java's anonymous classes can be treated as a slightly messier form of closures...

Tristam MacDonald - Software Engineer @ Amazon - [swiftcoding] [GitHub]

Posted 26 January 2013 - 10:26 AM

Speaking of type inference, how come this is "ambiguosly typed"?

-- test
test = do (lfsr 1 1)

-- pump through specified lfsr
| ((seed .&. 1) == 1) = (xor post mask)
| (otherwise) = (post)
where post = (shiftR seed 1)

Scraping test and punching in

> lfsr 1 1

Seems to work.

Also, I can't get the hang of working with the State monad, which I'm under the impression is the best one to use in this case.
I guess I'm trying to make a Functor or something.  I'm still a rookie programmer, so I don't really know.

I need state for a PRNG, obviously.  I just need one tuple for now, containing a mask Bits and some state Bits.
I was gonna newtype that, but it's throwing all kinds of crazy errors again, so I was just gonna wing it with Bits.
What I would really like to do is define a Mask type of Bits and a Step type of Bits, then combine them into a Lfsr tuple type.
The reason I want to do this is to catch myself putting Mask into Step or something awful.  That /would/ catch me, right?.

I can't find any good tutorials, mostly bad documentation with advanced commentary on the future of haskell.

The tutorials I can find are really specific to a hardly relevant topic and in depth in directions I can't understand.

This is obviously not a good language for beginners lol. (I do have some programming experience)
Can anyone help me some more?

Ultimately, my goal is to create a table of lfsrs, and either use locking mechanisms, or link them to each core, to ensure fast, random results.
That's why I have mask as a mutable variable - I worked really hard on conceiving an algorithm to quickly generate masks for me, which I think is pretty bad ass.

Edited by Blind Radish, 26 January 2013 - 10:34 AM.

### #9SamLowry  Members

Posted 27 January 2013 - 04:46 AM

(Apologies for the bad formatting, but I lack the patience to correct it once more, it's being screwed up repeatedly)

The error message is probably related to the fact that it can't deduce what the type of the literal 1 is. 1 could be an Int, an Integer, a Float, etc. Haskell knows it must be an instance of the Bits class, but that still leaves open a lot of possibilities. You can solve the problem by giving explicit type annotations.

test :: Integer
test = fsr 1 1

Also, I can't get the hang of working with the State monad, which I'm under the impression is the best one to use in this case.
I guess I'm trying to make a Functor or something.  I'm still a rookie programmer, so I don't really know.

I need state for a PRNG, obviously.  I just need one tuple for now, containing a mask Bits and some state Bits.
I was gonna newtype that, but it's throwing all kinds of crazy errors again, so I was just gonna wing it with Bits.
What I would really like to do is define a Mask type of Bits and a Step type of Bits, then combine them into a Lfsr tuple type.
The reason I want to do this is to catch myself putting Mask into Step or something awful.  That /would/ catch me, right?.

I'm not 100% certain of your intentions, I'm a bit confused, so I don't know if my answer will make sense to you. Bits is not a type, it is a type class. As far as I know, it is not possible to define a type which requires its constructor arguments to have types belonging to a certain class.

For example,

newtype Step = Step Bits

won't work since Bits is not a type. You actually want something like

i.e. "Mask parameterized in some type a that must be an instance of the class Bits", but this does not exist in Haskell. What you can do however, is this
newtype Step a = Step a
newtype Lfsr a = Lfsr (Mask a, Step a)

This does not enforce that the type of the Mask and Step are instances of Byte, but it will help you make the distinction between masks and steps. Haskell will give an error message if you put a step in a mask spot, or vice versa.

For a PRNG, you only need a part of the state monad's functionality. You can imagine the PRNG as being an infinite list of random numbers. Every time you need a random number, you grab it from the front of this list. This is a more general and would allow you to use different approaches to generating random numbers. The monad would look like this (I believe a similar one already exists in Haskell's standard library):
data PRNG r a = PRNG { runPrng :: [r] -> (a, [r]) }

return x = PRNG $\rs -> (x, rs) PRNG f >>= g = PRNG$ \rs -> let (a, rs') = f rs in runPrng (g a) rs'

rand :: PRNG r r
----------------
rand = PRNG (\rs -> (head rs, tail rs))

So, a function needing a source of random numbers is one that takes a list of random numbers and returns some result of arbitrary type a and a remaining list of random numbers, i.e. [r] -> (a, [r]). Combining two such functions is done by giving the rest list returned by the first function to the second function (this is what >>= does).

We can define a dumb PRNG as follows:
withSillyPRNG :: PRNG Integer a -> a
------------------------------------
withSillyPRNG (PRNG f) = fst $f [0..] and use it as follows: throwDie :: PRNG Integer Integer -------------------------------- throwDie = do x <- rand return$ x mod 6 + 1

throwDice :: Int -> PRNG Integer Integer
----------------------------------------
throwDice 0 = return 0
throwDice n = do x <- throwDie
y <- throwDice (n - 1)
return $x + y withSillyPRNG (throwDice 5) 15 generateList :: Int -> PRNG r [r] --------------------------------- generateList 0 = return [] generateList n = do x <- rand xs <- generateList (n - 1) return$ x : xs

withSillyPRNG (generateList 10)
[0,1,2,3,4,5,6,7,8,9]

A PRNG based on your lfsr (probably not as you intend to make it, but hey, it seems to generate numbers)
withLFSR :: Bits r => r -> r -> PRNG r a -> a
---------------------------------------------
withLFSR seed mask (PRNG f) = fst \$ f nums
where
nums = seed : map (lfsr seed) nums

withLFSR 1078 176 (generateList 10)
[1078,539,1339,1707,1891,1927,2037,1996,998,499]

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.