Loading ...
Sorry, an error occurred while loading the content.
 

Re: "ocaml_beginners"::[] Very basic list iteration kind of question

Expand Messages
  • Danny Yoo
    ... A hashtable might also be applicable: (******) # let h = Hashtbl.create 0;; val h : ( _a, _b) Hashtbl.t = # Hashtbl.add h (1, 1) 42;; - : unit =
    Message 1 of 6 , Mar 9, 2004
      On Tue, 9 Mar 2004, Matt Gushee wrote:

      > On Wed, Mar 10, 2004 at 12:10:57AM +0000, robin wrote:
      > >
      > > type link = {
      > > mac1: string;
      > > mac2: string;
      > > throughput: float;
      > > };;
      > >
      > > I want to store a collection of these 'link' records in a data
      > > structure. It's fine for the structure to be immutable.
      >
      > But it's not fine for it to be a list--as you would undoubtedly discover
      > for yourself eventually. The problem, of course, is that a list can
      > contain duplicates. I don't know what the data represent, but I'm
      > guessing that each pair of mac1 and mac2 values must be unique, and the
      > throughput value is arbitrary and non-unique.


      A hashtable might also be applicable:


      (******)
      # let h = Hashtbl.create 0;;
      val h : ('_a, '_b) Hashtbl.t = <abstr>
      # Hashtbl.add h (1, 1) 42;;
      - : unit = ()
      # Hashtbl.add h (2, 3) 17;;
      - : unit = ()
      # Hashtbl.find h (1, 1);;
      - : int = 42
      # Hashtbl.find h (100, 102);;
      Exception: Not_found.
      (******)


      So we can create a Hashtbl that maps from (string * string) 2-tuples to
      links. Hashtbl's are documented here:

      http://caml.inria.fr/ocaml/htmlman/libref/Hashtbl.html


      Hope this helps!
    • Karl Zilles
      ... You give very little information about how you want to use the data structure. If you just want to access things efficiently in the way you describe, then
      Message 2 of 6 , Mar 9, 2004
        robin wrote:
        > I define a record as:
        >
        > type link = {
        > mac1: string;
        > mac2: string;
        > throughput: float;
        > };;
        >
        > I want to store a collection of these 'link' records in a data structure. It's fine for the structure to be immutable. What I want to do is write a function defined as :
        >
        > given mac1 and mac2,
        > if the 'table' contains a link that matches mac1 and mac2, return the throughput
        > otherwise return 0.
        >
        > let throughput mac1 mac2 = ?
        >
        > Can anyone advise me on the best way to express this? I'm using o'caml as a way to experiment with an algorithm to determine whether it's correct and effective, so I'm interested in idiomatic clarity, and simplicity over performance.

        You give very little information about how you want to use the data
        structure. If you just want to access things efficiently in the way you
        describe, then as another poster noted, a hashtable may be the way to go:

        let link_table = Hashtbl.create 1000;;
        let add link = Hashtbl.replace link_table (link.mac1,link.mac2)
        link.throughput;;
        let throughput mac1 mac2 = (Hashtbl.find link_table (mac1,mac2));;
      • John Goerzen
        ... OK, I ll assume you re storing them in a list. For instance: let l = [{mac1 = asdf ; mac2 = foo ; throughput = 0.0}];; Now then [ WARNING: untested code
        Message 3 of 6 , Mar 9, 2004
          On Wed, Mar 10, 2004 at 12:10:57AM +0000, robin wrote:
          > I may be thinking about things in a procedural/oo way so any guidance about the right approach would be appreciated.
          >
          > I define a record as:
          >
          > type link = {
          > mac1: string;
          > mac2: string;
          > throughput: float;
          > };;
          >
          > I want to store a collection of these 'link' records in a data structure. It's fine for the structure to be immutable. What I want to do is write a function defined as :

          OK, I'll assume you're storing them in a list. For instance:

          let l = [{mac1 = "asdf"; mac2 = "foo"; throughput = 0.0}];;

          Now then [ WARNING: untested code ], here's the search function you
          want:

          let comparemac mac1 mac2 macrecord =
          macrecord.mac1 = mac1 && macrecord.mac2 = mac2;;

          let searchmac mac1 mac2 maclist =
          try
          let res = List.find (comparemac mac1 mac2) maclist in
          res.throughput
          with Not_found -> 0.0;;

          Here's how it works. First, we define a function comparemac that takes
          a mac1, a mac2, and a record. It returns true if there's a match and
          false otherwise.

          Next, the searchmac function takes the two search terms and a list of
          records. It calls List.find on that list. List.find takes two
          parameters: a function and a list. It calls the function for each
          element in the list. If the function returns true, it stops and returns
          that element. If the function returns false, it continues searching.
          If true is never returned, it raises the Not_found exception.

          If we do have a hit, it gets stored in res -- and we return
          res.throughput. If there was no hit, 0.0 gets returned.

          Notice how comparemac takes three parameters but we only listed two.
          List.find supplies the third one.

          You could write the above two functions more concisely like this:

          let searchmac mac1 mac2 maclist =
          try
          (List.find (function x -> x.mac1 = mac1 && x.mac2 = mac2) maclist).throughput
          with Not_found -> 0.0;;

          See what's happening? We defined a function inline, that takes one
          parameter. It didn't need to take three parameters since mac1 and mac2
          were already in scope. The "throughput" field of the return value of
          List.find is then returned, and again, if Not_found is raised, 0.0 gets
          returned.

          Slick, eh?

          FYI, you could define List.find yourself: [NOTE: untested code]

          let rec listfind func searchlist = match searchlist with
          [] -> raise Not_found
          | head :: tails -> if (func head) then head else listfind func tails;;

          Can you follow that one? We declare a function taking two args: a
          function and a list to search. If the list to search is empty, we raise
          the Not_found exception. Otherwise, the list is split into two pieces:
          the single item "head" and the list of all remaining records "tails".

          If (func head) returns true, then we return head; otherwise we return
          the result of listfind on tails. This is a nice functional way to
          implement List.find, and I wouldn't be surprised if the standard library
          implemented it almost word for word like this.

          > Can anyone advise me on the best way to express this? I'm using
          > o'caml as a way to experiment with an algorithm to determine whether
          > it's correct and effective, so I'm interested in idiomatic clarity,
          > and simplicity over performance.
          >
          > Any help would be much appreciated.
          >
          > Warm Regards,
          >
          > -Robin Barooah
          >
          >
          >
          >
          >
          > ------------------------ Yahoo! Groups Sponsor
          > ---------------------~--> Buy Ink Cartridges or Refill Kits for your
          > HP, Epson, Canon or Lexmark Printer at MyInks.com. Free s/h on orders
          > $50 or more to the US & Canada.
          > http://www.c1tracking.com/l.asp?cid=5511
          > http://us.click.yahoo.com/mOAaAA/3exGAA/qnsNAA/saFolB/TM
          > ---------------------------------------------------------------------~->
          >
          > Archives up to July 22, 2003 are also at
          > http://www.connettivo.net/cntprojects/ocaml_beginners/ocaml_beginners_archive_220703/
          > The archives of the very official ocaml list (the seniors' one) can be
          > found at http://caml.inria.fr Attachments are banned and you're asked
          > to be polite, avoid flames etc. etc.p://caml.inria.fr Attachments are
          > banned and you're asked to be polite, avoid flames etc. etc. Yahoo!
          > Groups Links
          >
          >
          >
          >
          >
        Your message has been successfully submitted and would be delivered to recipients shortly.