OCaml 函数检查列表是否为具有 floor(n/2) 递归调用且没有列表分配的回文

Question

uni上有这个任务，研究了好久，就是没找到，这个函数怎么写。我需要它来检查列表是否为回文，最多递归地调用自身 floor(n/2) 次并且不分配任何辅助列表（因此我可以不使用列表构造函数）。有任何想法吗？老实说，我想要一个算法而不是一个完整的解决方案。

Answer 1

您可以使用递归辅助函数

在进入的路上，接受两个参数：列表的剩余部分，以及距离要检查的列表开头两倍远的列表剩余部分。
在要检查的列表中间达到其基本情况（当第二个列表变为空时，或者 - 在奇数长度的情况下 - 只有一个元素）
在出路时，returns 一个 option 一个列表，其余的仍然需要反向检查是否相等 - 或者 None 当回文不匹配时

示例：

// in
hannah hannah
 annah   nnah
  nnah     ah
   nah       
// out
  n <-> nah
 a  <->  ah
h   <->   h

Answer 2

我想出了这个并且有效：

let palindrom l =
let rec aux l0 l1 =
    match (l0, l1) with
    | _,[] -> (true,[])
    | hd :: tl, [x] -> (hd = x, tl)
    | _, hd1 :: tl1 -> let (pal, ll) = aux l0 tl1 in
          match ll with
          | [] -> (pal, [])
          | hd::tl -> (pal && hd1 = hd, tl) in
match l with
[] -> true
| _ -> fst (aux l l)

OCaml 函数检查列表是否为具有 floor(n/2) 递归调用且没有列表分配的回文

OCaml function to check if list is palindrome with floor(n/2) recursive calls and no list allocation

ocaml

list

palindrome