catamorphism/foldを使用して、構造的に再帰的な関数を明示的に再帰的に記述することはできませんか?

特に、再帰的な振る舞いや複数のF-algebrasを変更する条件付きの関数を考えています。

halting_search :: int -> (a -> bool) -> (a -> a) -> a -> Maybe a
halting_search 0 f_test f_next_candidate candidate = Nothing
halting_search (S n) f_test f_next_candidate candidate = case (f_test candidate) of
  true => Just candidate
  false => halting_search n f_test f_next_candidate (f_next_candidate candidate)

これは cata
演算子を使って書くことができますか?私が求めているのは、かなり表現力があるが過度に表現力のない機能的な言語を必要としているからであり、明示的な再帰を許さないようにする方法のように思えるが、
cata をプリミティブ関数。

ベストアンサー

あなたの関数は n
で完全に構造的に再帰的です。したがって、自然数の対数変換にするのは表記の変更にすぎません。

type nat = Z | S of nat 

(* cata : α → (α → α) → nat → α *)                      
let rec cata z s = function
  | Z -> z 
  | S n -> s (cata z s n)

(* halting_search : nat → (α → bool) → (α → α) → α → α option *)             
let halting_search n = 
  cata (fun test next seed -> None)
       (fun recur test next seed -> 
         if test seed then 
           Some seed
         else 
           recur test next (next seed))
       n

高次関数と厳密に正のデータ型を持つ言語の場合、折り返しを持つと表現力が構造的再帰を可能にするのと同等です。しかし、それは効率の面で同等ではありません。折りたたみをしている場合は、Peanoの自然数に先行関数を実装するのはO(n)ですが、ケースフォームがある場合はO(1)です。

(* This is linear time! *)
pred : nat -> nat option 
let pred n = cata None (function 
                           | None   -> Some Z 
                           | Some n -> Some (S n)) n 

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です