Need some help with Higher Order Functions in Scheme - Computer Technical Help

Two Plus Two Forums Other Topics Computer and Technical Help

Need some help with Higher Order Functions in Scheme

Post Reply Subscribe

...

04-14-2013 , 08:45 PM

derada4

old hand

Join Date: Feb 2011 Posts: 1,544

I'm working on this assignment that is a spell-checker using hash functions, to avoid a tl;dr I will cut right to the chase:

I have a function called key that takes a word as a list "hello" = '(h e l l o), and generates a key (integer). I also have a function called flip that takes '(h e l l o) and flips it to '(o l l e h), which simplified my key function.

I've tested these two functions independently and they work fine. Functions are in spoilers in case you are interested but the function body isn't too relevant to my question.

Spoiler:

Now the main problem is I have to take the key, and generate a hash value. In the assignment I am given the skeleton of a function:

Quote:

(define gen-hash-division-method (lambda (size)))

as well as:

Quote:

(define hash-1 (gen-hash-division-method 701))

The function gen-hash-division-method needs to compute (modulo key size)

What I have coded myself is:

Quote:

(define gen-hash-division-method (lambda (size)
(lambda (w) (modulo key(flip(w)) size))))

But the problem is that whenever I call:

Quote:

(hash-1 '(h e l l o))

(This is the given format we have to use)

I keep getting this error:

Quote:

procedure application: expected procedure, given: (h e l l o) (no arguments)

I have honestly spent over 6 hours trying to figure out why this isn't working, and experimenting with writing the gen-hash-division-method different ways and am just running into a brick wall...

Last edited by derada4; 04-14-2013 at 08:51 PM.

Quote

04-14-2013 , 09:32 PM

derada4

old hand

Join Date: Feb 2011 Posts: 1,544

I got it!

key(flip(w)) should be (key(flip w))

Wow lol can't believe it was that minor

Quote

04-14-2013 , 09:44 PM

daveT

S.A.G.E. Master

Join Date: Jun 2005 Posts: 23,955

Scheme is not C. I fixed the upper function to look more Scheme-y:

(also use code tags, which are represented by the # symbol in the advanced editing mode here on 2+2)

Code:

(define flip
  (lambda (s)
    (if (null? s)
        '()
      (append (flip (cdr s)) ('(car s))))))

(define key
  (lambda (w)
;;first check if the list (word) is null
    (if (null? w)
        0
      ;;this is the base case when there is only one letter left
      (if (null? (cdr w))
          (+ (* 33 5381) (ctv (car w)))
;;this is the recursive step
        (+ (* 33 (key (cdr w))) (ctv (car w)))

Are you using an editor with parenthesis matching?

irt to the gen-hash-method, yes, it will bonkers out because of the last line. See the comments:

Code:

(define gen-hash-division-method
  (lambda (size)
    (lambda (w) (modulo key (flip(w)) size)))))

;;; Let's rewrite this:

(define gen-hash-division-method
  (lambda (size)
    ;; do you understand what is happening here?
    ;; do you know what a closure is? 
    (lambda (w)
      ;;; if you want to call a function in Scheme, you have
      ;;; to wrap it in parens:
      ;; you do not wrap args in parens: 
      (modulo (key (flip w)) size))))

I think you're confused by how to call functions in Scheme. The syntax that you use in this case:

(+ 3 4)

or

(cdr my-list)

is the same exact syntax that you use to call a function that you have created:

(my-function-rocks my-list)

The idea of Scheme (or any Lisp) is to create a program that is syntactically consistent, where the functions you create are not apparent from the functions built in to the program.

If you don't mind me asking, where are you learning to write this language? The syntax is all bonkers and it looks like a fairly difficult assignment for your comfort level of this language.

Quote

04-14-2013 , 09:45 PM

daveT

S.A.G.E. Master

Join Date: Jun 2005 Posts: 23,955

Quote:

Originally Posted by derada4

I got it!

key(flip(w)) should be (key(flip w))

Wow lol can't believe it was that minor

Find a real text editor. It'll save you sooo much pain.

Last edited by daveT; 04-14-2013 at 09:46 PM. Reason: Seriously, the code style hurts mine eyes.

Quote

04-15-2013 , 09:15 AM

derada4

old hand

Join Date: Feb 2011 Posts: 1,544

thanks for the detailed response.

I have been using Notepad++ and when I copy+pasted it into my post the tabbing was all screwed up. In my file I do have it written out in a more Scheme-y way, almost exactly the way you restructured it.

Thanks for looking at the key function. And yes, throwing the cdr is the intent in that spot.

This is an assignment for a Principles of Programming Languages class, its a mid-level CS class. Haven't really had too many problems with this assignment or previous ones, I guess just a total brain fart with that little syntax issue.

Thanks again, I really appreciate the detailed response.

Quote

04-16-2013 , 09:55 PM

derada4

old hand

Join Date: Feb 2011 Posts: 1,544

Ok I have another question, my program is basically set up like this:

Code:

(define spellchecker
  (lambda (dictionary hash)
     (lambda (word)
        (isWordInTable word (createTable dictionary hash)))))

and

Code:

(define spellchecker-1 (spellchecker dict1 hash1))

The spell checker is called as so:

Code:

(spellchecker-1 '(h e l l o))

Currently, everytime we make a call to spellchecker-1, the hash table is created and recreated every single time.

How can I create the hashtable the first time spellchecker-1 is called, then store(?) it so I don't keep rebuilding it every time I call spellchecker-1??

Quote

04-16-2013 , 10:19 PM

daveT

S.A.G.E. Master

Join Date: Jun 2005 Posts: 23,955

Are you asking if you can store it in an external file and call it as such?

Once you restart a program, you are destroying all the values in the namespace, there is nothing you can do about that no matter what programming language you are using.

You may also want to consider using Dr Racket so you have something analogous to a REPL. You'll be able to call that table and hash without rebuilding it as long as the program is running. http://racket-lang.org/ It may take a bit of setup depending on what your class requires.

Also, don't be confused by the name "createTable." createTable is not a function that creates a new table*. It is the name of the value where the procedure of createTable is stored. Since values do not mutate in Scheme*, you are not creating new function-calls as you would in other languages, you are calling a value that stores the entire table. You can't destroy that table* and create a new table.

The same thing goes for the hashes. As long as you have:

Code:

(define hash1 ....)

somewhere in your code, it is an immutable value and it will always be there when you call it.

*caveats that I don't want to write here, but you'll discover in due time if you haven't been exposed to (set!) yet.

Quote

04-16-2013 , 10:39 PM

derada4

old hand

Join Date: Feb 2011 Posts: 1,544

Ok so say I fire up scheme by calling mzscheme in bash (Haven't used DrRacket because when they grade it they do it right in bash so I want to make sure it works that way).

I then load my .ss file that defines all of my functions.

Then I enter:

Code:

>(define spellchecker-1 (spellchecker dict1 hash1))
>(spellchecker-1 '(h e l l o))

and I get:

Code:

>#t

Awesome. Now I enter:

Code:

(spellchecker-1 '(h e l o))

and I get:

Code:

>#f

You're saying that the second time I call spellchecker-1, I don't actually call createTable again, it just automatically reuses the one from the original spellchecker-1 call?

I'm not worried about exiting the program, just the scenario I described above.

If I understand correctly...

When I enter

Code:

>(define spellchecker-1 (spellchecker dict1 hash1))

createTable inside of spellchecker executes with the parameters passed into it, and then the REST of spellchecker executes when I enter

Code:

>(spellchecker-1 '(h e l l o))

Quote

04-16-2013 , 11:27 PM

daveT

S.A.G.E. Master

Join Date: Jun 2005 Posts: 23,955

As long as you get the word "execute" out of your mind, you're okay.

There is no difference between:

Code:

(define x 5)

and

Code:

(define y createTable)

nothing above mutates and nothing is recreated or executed. They are simply values and the difference between 5, createTable, and hash1 is visual if you simply consider them values and accept that they hold the same general properties of immutability. Nothing disappears and reappears in the program. You can even experiment with that and use the above binding and see that it never changes if you are willing to splash around a bit.

Thus, your summary here is correct:

Quote:

You're saying that the second time I call spellchecker-1, I don't actually call createTable again, it just automatically reuses the one from the original spellchecker-1 call?

Quote

04-17-2013 , 11:49 AM

#10

derada4

old hand

Join Date: Feb 2011 Posts: 1,544

Ok I think I get it...

So when we enter:

Code:

>(define spellchecker-1 (spellchecker dict1 hash1))

spellchecker-1 is the procedure returned by passing dict1 and hash1 through spellchecker.

And then when we enter:

Code:

>(spellchecker-1 '(h e l l o))

We are passing '(h e l l o) into the procedure that is spellchecker-1

Quote

04-18-2013 , 02:37 AM

#11

daveT

S.A.G.E. Master

Join Date: Jun 2005 Posts: 23,955

I'm not sure what language you are familiar with, but this Python code represents what you are attempting to understand:

Code:

k = ["hello", "goodbye", "stay"]
v = [1, 2, 3]
d = {}

for i in range(len(k)):
  d[k[i]] = v[i]

print(d)

>>> {'hello': 1, 'goodbye': 2, 'stay': 3}
>>> d["hello"]
1

Is d a procedure?

Try this:

Code:

def createDict(k, v):
  d = {}
  for i in range(len(k)):
    d[k[i]] = v[i]
  return d

k = ["hello", "goodbye", "stay"]
v = [1, 2, 3]

k1 = ["Joe", "Mary", "Steve"]
v1 = [1, 2, 3]

a = createDict(k, v)
a1 = createDict(k1, v1)

That is all you are doing here, really. You are mapping the returned value of the function to the values of a and a1.

When I:

Code:

>>> a['hello']
1
>>> a1['Steve']
3

I'm not calling any procedure or function. I am calling a to retrieve the values bound to a. The fact that the values were generated by a function is irrelevant.

Quote

04-18-2013 , 02:03 PM

#12

derada4

old hand

Join Date: Feb 2011 Posts: 1,544

yesss now I see

Quote

Post Reply Subscribe

...