7 Replies - 2743 Views - Last Post: 28 February 2013 - 08:01 AM

#1 yeris  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 8
  • Joined: 23-January 13

OCaml: basics

Posted 27 February 2013 - 05:10 PM

Hi!

So this is my first encounter with functional languages, and I have some hard time to get the idea. I have a basic question to " Write a function that repeats a given element the prescribed number of times and returns the result as a list". So this is my concept, but I have a feeling that this is pure rubbish:

let rec duplicate x y = 
let l1 in
   if y=0 then l1
   else x::l1 duplicate x y-1;;   



and yup, it doesn't work. I think that second line ,where I try to create a list, is a bad idea. I also tried to treat x and y as (x,y), but it did't help.
I understand that it should do something like this 'a * int -> 'a list , but I have to create and change a list inside a function, and I don't know how to think about it.

Is This A Good Question/Topic? 0
  • +

Replies To: OCaml: basics

#2 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2153
  • View blog
  • Posts: 3,315
  • Joined: 21-June 11

Re: OCaml: basics

Posted 27 February 2013 - 05:47 PM

You're right that line 2 doesn't make sense. The syntax of let is let variable = value in ... - the = value part is not optional. Since variables in OCaml are immutable¹, it makes no sense to define a variable without giving it a value. You probably meant to write let l1 = [] in, but that would also not be very useful - saying l1 anywhere would just be equivalent to saying [], so you can just as well say that. Really you don't need the l1 variable at all.

The other problem is on line 4. x :: l1 duplicate x y-1. This is calling the function l1 (which isn't actually a function - so you get a type error) with the arguments duplicate, x and y. It then subtracts 1 from the result of the function call and prepends x to it. As you can see, there's all sorts of type errors in there (prepending to something implies that it's a list, but subtracting implies that it's a number).

You should put parentheses around y-1, so it will subtract 1 from y instead of subtracting one from the result of the function call². That will solve one of your problems.

You seem to think that x::l1 will mutate l1 to contain the element x and you want x::l1 and duplicate x y-1 to be interpreted as two separate expressions that execute after each other. But that's not how it works. Lists are immutable in Ocaml. And executing independent expressions after each other without using their results, makes no sense if the expressions have no side effects.

You should just call duplicate x (y-1) and then prepend x to the result of that recursive call.

¹ At least local variables are - an object's or record's fields can be mutable if declared as such, but that's not relevant here.

² f x-1 is parsed as (f x) - 1, not f (x-1).

This post has been edited by sepp2k: 27 February 2013 - 05:47 PM

Was This Post Helpful? 3
  • +
  • -

#3 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1156
  • View blog
  • Posts: 2,538
  • Joined: 05-May 05

Re: OCaml: basics

Posted 27 February 2013 - 05:47 PM

Well, first thing, it would be helpful to name your variables to something a little more understandable. I'm sure you can do better than "l1".

I really don't know OCaml, but I know functional programming. It appears that you've introduced a local let binding "l1" but you never initialize it or anything. What's its use? Your base case "y=0" is correct. Then I see you return "l1", so is "l1" an empty list here? You should be returning an empty list. Like I said I don't the semantics of OCaml, but that looks problematic. You could have simply said.

if n = 0 then []


The else clause should append the element onto a list that's one element smaller in size. E.g

else elem::make_list(elem, n-1)


Hope that helps.
Was This Post Helpful? 3
  • +
  • -

#4 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 8028
  • View blog
  • Posts: 13,741
  • Joined: 19-March 11

Re: OCaml: basics

Posted 27 February 2013 - 09:52 PM

Quote

Write a function that repeats a given element the prescribed number of times and returns the result as a list


Think recursively: reduce the problem to a base case and return an obvious development from that base case. I don't like your function's signature, it's not very informative as blackcompe points out. So let's call it:
fun dup (value, times) = 


What happens if I call this like this?

dup ("foo", 0);



You should be able to give me that special case quite easily.

And you know that for any list l which is the result of

dup ("foo", n); 


it's easy to see that

dup ("foo", n+1); 


will just be the list l with another "foo" tacked onto the front of it, right?

So since you know the list l for the case of times=0, you should be able to solve times=1 by reducing it to the case of times = 0 and tacking on a "foo" to the result of that. And the same will go for any positive integer value of times.
Was This Post Helpful? 2
  • +
  • -

#5 yeris  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 8
  • Joined: 23-January 13

Re: OCaml: basics

Posted 28 February 2013 - 02:45 AM

wow! Thank you all, I did't expect to see so detailed comments!
OK, so after reading and analyzing all your post I came up with this:
let rec duplicate value times=
if times=0 then []
else value::duplicate value (times-1);;



And it works.
Was This Post Helpful? 1
  • +
  • -

#6 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 8028
  • View blog
  • Posts: 13,741
  • Joined: 19-March 11

Re: OCaml: basics

Posted 28 February 2013 - 06:15 AM

Perfect. It might please you but it should not surprise you to know that that is exactly the function that I wrote in my interpreter when I read your post. (except for the extra semicolon, which may be a typo)

The basic concept of recursion is on display here: you have a base case, and you take any input and simplify towards it. As long as every recursive call looks more like the base case, and you never diverge, you can solve a lot of problems with recursion.

For example, you could count the number of items in a list, or count the number of times a particular item appears in a list. Or (more complicated) you could count the number of times some member of list a appears in list b. (so for a = [1,2,3] and b = [1,4, 6, 8, 2] you'd return 2)
And of course you can do useful work too, like writing parsers and stuff.

If you want to review recursion in more depth, you might consider picking up a book called "The Little Schemer", which although it's written to Scheme and not *ML will give you a tremendous workout in recursion and some related concepts. The Scheme that's required is not difficult, in fact I think you could start the book without knowing anything of the language and be just fine.
The same authors also have a book called The Little MLer, which is more aimed at the ML family - I'm working my way through that one right now and it covers similar ground, but TLS might be a bit more thorough and obsessive about recursive thinking.
Wouldn't hurt to go through both, honestly.
Was This Post Helpful? 2
  • +
  • -

#7 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2153
  • View blog
  • Posts: 3,315
  • Joined: 21-June 11

Re: OCaml: basics

Posted 28 February 2013 - 06:31 AM

View Postjon.kiparsky, on 28 February 2013 - 02:15 PM, said:

(except for the extra semicolon, which may be a typo)


In the Ocaml interpreter you need ;; to terminate input. If you only enter one semicolon (or two semicolons with whitespace between them), it will keep waiting for more input until you enter ;;.
Was This Post Helpful? 1
  • +
  • -

#8 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 8028
  • View blog
  • Posts: 13,741
  • Joined: 19-March 11

Re: OCaml: basics

Posted 28 February 2013 - 08:01 AM

Oh, okay. Weird, but okay. SML would probably pitch a fit if you gave it an extra semicolon - titchiest language I ever did see, that one.

This post has been edited by jon.kiparsky: 28 February 2013 - 08:02 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1