問題1

forループ、whileループ、および再帰を使用して、リスト内の数字の合計を計算する3つの関数を記述せよ。

F#はミュータブルな変数も定義できるので、forループとwhileループではそのような書き方をわざとしました。

let q1_for xs =
    let mutable sum = 0
    for i in xs do sum <- sum + i
    sum

let q1_while xs =
    let mutable sum = 0
    let mutable ys = xs
    while not (List.isEmpty []) do
        sum <- sum + List.head ys
        ys <- List.tail ys
    sum

let q1_recc xs =
    let rec q1_recc acc = function
    | []    -> acc
    | y::ys -> q1_recc (acc + y) ys
    q1_recc 0 xs

でもふつうは List.sum 関数で一発ですよね。

問題2

交互に要素を取ることで、2つのリストを結合する関数を記述せよ。例えば [a, b, c] と [1, 2, 3] という2つのリストを与えると、関数は [a, 1, b, 2, c, 3] を返す。

let q2_flatZip xs ys =
    List.zip xs ys |> List.collect (fun (x,y) -> [x; y])

問題3

最初の100個のフィボナッチ数のリストを計算する関数を記述せよ。定義では、フィボナッチ数列の最初の2つの数字は0と1で、次の数は前の2つの合計となる。例えば最初の10個のフィボナッチ数列は、0, 1, 1, 2, 3, 5, 8, 13, 21, 34となる。

100個ということなので、符号なし64ビット整数を使いました。

let q3_fib100 =
    let fib = Seq.unfold (fun (a, b) -> Some(a, (b, a+b))) (0UL, 1UL)
    fib |> Seq.take 100 |> Seq.toList

問題4

正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。例えば、 [50, 2, 1, 9] が与えられた時、95021 が答えとなる。

効率よく計算する方法を考えていたら時間をたくさん使ってしまったのであきらめました。すべての候補を数え上げて、降順にソートして先頭を取るようにしました。

let q4_biggest (xs: int list) =
    let rec select = function
        | []    -> []
        | [x]   -> [(x,[])]
        | x::xs -> (x,xs) :: List.map (fun (y,ys) -> (y,x::ys)) (select xs)
    let mapAdd x = List.map (fun xs -> x::xs)
    let rec perm = function
        | [] -> [[]]
        | xs -> select xs
                |> List.collect (fun (y,ys) -> mapAdd y (perm ys))
    perm xs
    |> List.map (List.collect (fun i -> i.ToString() |> Seq.toList))
    |> List.sortWith (fun x y -> Operators.compare y x)
    |> List.head
    |> System.String.Concat
    |> (string >> int)

（追記）上の解法は数値を文字列化して桁を取り出したり、また文字列に戻して数値化したりしているのが美しくないので、文字列を使わないように直しました。

let q4_biggest =
    let rec select = function
        | []    -> []
        | [x]   -> [(x,[])]
        | x::xs -> (x,xs) :: List.map (fun (y,ys) -> (y,x::ys)) (select xs)
    let mapAdd x = List.map (fun xs -> x::xs)
    let rec perm = function
        | [] -> [[]]
        | xs -> select xs
                |> List.collect (fun (y,ys) -> mapAdd y (perm ys))
    let digits x =
        let rec digits x = if x < 10 then [x] else (x%10) :: digits (x/10)
        digits x |> List.rev
    perm
    >> List.map (List.collect digits)
    >> List.sortWith (fun x y -> Operators.compare y x)
    >> List.head
    >> List.reduce (fun x y -> 10*x+y)

問題5

1, 2, …, 9の数をこの順序で、”+”、”-“、またはななにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる。

こちらも全ての候補を数え上げて、条件に合うもののみ残すようにフィルタしました。

let q5_list100 =
    let all : (char * int) list list =
        let rec ops = function
        | 0 -> [[]]
        | i -> List.collect (fun xs -> ['+'::xs; '-'::xs; ' '::xs]) (ops (i - 1))
        ops 8
        |> List.map (fun xs -> List.zip (' '::xs) [1..9])
    let answerIs100 : (char * int) list list =
        let calc =
            let initial = ((+), 0, 0)
            let folder (f, s, r) (c, x) =
                match c with
                | '+' -> ((+), f s r,      x)
                | '-' -> ((-), f s r,      x)
                | _   -> (  f,     s, 10*r+x)
            List.fold folder initial
            >> fun (f, s, r) -> f s r
        List.filter (fun xs -> calc xs = 100) all
    let toString : (char * int) list -> string =
        let toChar x = char (int '0' + x)
        let initial = []
        let folder cs (c, x) =
            match c with
            |'+'|'-' -> toChar x :: c :: cs
            | _      -> toChar x :: cs
        List.fold folder initial
        >> List.rev
        >> System.String.Concat
    List.map toString answerIs100

「ソフトウェアエンジニアならば1時間以内に解けなければいけない5つの問題」をF#で

問題1

問題2

問題3

問題4

問題5