Как преобразовать такую ​​функцию lisp в ocaml?

Question

Функция «good-red» используется для вычисления 18 самых высоких частотных чисел из файла ssqHitNum.txt.

(defun good-red ()
(let ((tab (make-hash-table)) (res '()) (nums) (sort-res))
    (dotimes (i 33) (setf (gethash (+ i 1) tab) 0))
    (with-open-file (stream "ssqHitNum.txt")
        (loop :for line = (read-line stream nil)
             :until (null line)
             :do
                (setq nums (butlast (str2lst (subseq line 6))))
                (dolist (n nums) (incf (gethash n tab)))
                ))
    (maphash #'(lambda (k v) (push (cons k v) res)) tab)
    (setq sort-res (sort res #'> :key #'cdr))
    ;(print sort-res)
    (subseq (mapcar #'car sort-res) 0 18)))

$ head ssqHitNum.txt

10000 7 12 18 19 22 28 4
10000 16 17 23 26 31 32 11
10000 3 4 18 22 24 29 11
10000 4 9 10 18 29 32 8
10000 5 7 10 14 17 25 11

Числомежду 1 и 33. Использую ли я hashtab и сканирую файл построчно, как это делает код Common Lisp в ocaml?Или есть более элегантный способ использования ocaml?

Любое предложение приветствуется!

Answer 1

FWIW, в F # 3.0 вы можете просто написать это так:

System.IO.File.ReadLines @"ssqHitNum.txt"
|> Seq.collect (fun s -> s.Split ' ' |> Seq.skip 1)
|> Seq.countBy id
|> Seq.sortBy (fun (_, p) -> -p)
|> Seq.take 18

В OCaml я бы начал с написания этих полезных библиотечных функций с нуля:

let readAllLines file =
  let lines = ref [] in
  let input = open_in file in
  begin
    try
      while true do
        lines := input_line input :: !lines
      done
    with
    | End_of_file ->
        close_in input
  end;
  List.rev !lines

let collect f xs =
  List.concat (List.map f xs)

let countBy f xs =
  let counts = Hashtbl.create 100 in
  let find key = try Hashtbl.find counts (f key) with Not_found -> 0 in
  let add key = Hashtbl.replace counts (f key) (1 + find key) in
  List.iter add xs;
  Hashtbl.fold (fun k n kns -> (k, n)::kns) table []

let sortBy f xs =
  List.sort (fun x y -> compare (f x) (f y)) xs

let rec truncate n xs =
  match n, xs with
  | 0, _ | _, [] -> []
  | n, x::xs -> x::truncate (n-1) xs

let rec skip n xs =
  match n, xs with
  | 0, xs -> xs
  | n, [] -> []
  | n, _::xs -> skip (n-1) xs

let (|>) x f = f x

let id x = x

и затем напишите так же:

readAllLines "ssqHitNum.txt"
|> collect (fun s -> split ' ' s |> skip 1)
|> countBy id
|> sortBy (fun (_, p) -> -p)
|> truncate 18

F # все еще лучше, потому что строки читаются по требованию, тогда как мой OCaml считывает все в память заранее.

Answer 2

С той же точки зрения высокого уровня, используя Батареи :

open Batteries_uni

let freq file best_n =
  let table = Hashtbl.create 100 in
  let freq_num num =
    Hashtbl.replace table num (1 + Hashtbl.find_default table num 0) in
  let freq_line line =
    let nums = List.tl (String.nsplit line " ") in
    List.iter freq_num nums in
  Enum.iter freq_line (File.lines_of file);
  let cmp (_,freq1) (_,freq2) = (* decreasing *) compare freq2 freq1 in
  Hashtbl.enum table |> List.of_enum
    |> List.sort ~cmp
    |> List.take best_n

Для тестирования с верхнего уровня:

#use "topfind";;
#require "batteries";;
#use "/tmp/test.ml";;
test "/tmp/test.txt" 18;;

Answer 3

Как спросил z_axis, здесь есть другое решение, использующее только базовую библиотеку, распространяемую с компилятором OCaml. Это немного более многословно из-за отсутствия некоторых вспомогательных функций.

let freq file best_n =
  let table = Hashtbl.create 100 in
  let freq_num num =
    Hashtbl.replace table num
      (1 + try Hashtbl.find table num with Not_found -> 0) in
  begin
    let input = open_in file in
    try while true do
        let line = input_line input in
        let nums = List.tl (Str.split (Str.regexp " +") line) in
        List.iter freq_num nums
    done with End_of_file -> close_in input
  end;
  let sorted =
    let cmp (_,freq1) (_,freq2) = (* decreasing *) compare freq2 freq1 in
    List.sort cmp (Hashtbl.fold (fun k x li -> (k,x)::li) table []) in
  (* take not tail-rec, not a problem for small n such as n=18 *)
  let rec take n = function
    | li when n = 0 -> []
    | [] -> []
    | hd::tl -> hd :: take (n - 1) tl in
  take best_n sorted

Модуль регулярных выражений Str не связан по умолчанию, даже если он находится в пути поиска по умолчанию, поэтому вы должны явно скомпилировать программу с str.cma (для ocamlc) или str.cmxa (для ocamlopt). На верхнем уровне, #use "topfind";;, тогда будет #require "str";;.

Answer 4

С фиксированным набором маленьких целых чисел может быть проще использовать массив:

   let good_red () =
      let a = Array.make 33 0 in
      let bump i = a.(i-1) <- a.(i-1) + 1 in
      let rec iter_lines fh =
         try
            let words = Str.split (Str.regexp " +") (input_line fh) in
            List.iter bump (List.map int_of_string (List.tl words));
            iter_lines fh
         with End_of_file -> () in
      let fh = open_in "ssqHitNum.txt" in
      iter_lines fh;
      close_in fh;
      let b = Array.mapi (fun i freq -> (i+1,freq)) a in
      Array.sort (fun (i1,f1) (i2,f2) -> compare f2 f1) b;
      Array.sub b 0 18;;

   try
   Array.iter (fun (i,freq) -> Printf.printf "%2d %2d\n" freq i) (good_red ())
   with Invalid_argument _ -> print_endline "bad input"

Как упоминает Гаш, вам нужно скомпилировать с str.cma или str.cmxa.

Answer 5

Я не уверен, что понимаю проблему, которую вы хотите решить.(Почему все ваши входные строки начинаются с 10000?)

Если вы просто хотите найти 18-е числа с самой высокой частотой, вам не нужно читать построчно (и это верно в Lisp, в C, в Ocaml, ...), и Ocaml's Scanf.scanf "%d" (fun x -> ...) может сделать ввод.

И использование Hashtbl.t целесообразно в Ocaml.