こんにちは！
昨日に引き続き、Rustの学習メモです。
今日は、Rustの文法を手に馴染ませるため、様々なアルゴリズムにチャレンジしたいと思います。
Rustを始めてまだ１週間程度ですので、不十分なコードあるかもしれませんが、ご容赦ください。
ルール
- 対象のアルゴリズムを実装するコードを、ChatGPTにHaskellで書いてもらう
- そのコードを、Rustで可能な限り再現する
純粋関数型言語であるHaskellのコードに、どこまで近づけるか！
チャレンジしていきたいと思います！
基本
まずは基本的なやつから！
階乗
Haskell
fact :: Int -> Int
fact 0 = 1
fact n = n * fact (n - 1)
Rust
fn fact(n: i32) -> i32 {
match n {
0 => 1,
_ => n * fact(n - 1)
}
}
最大公約数（ユークリッドの互除法）
Haskell
gcd' :: Int -> Int -> Int
gcd' a 0 = a
gcd' a b = gcd' b (a `mod` b)
Rust
fn gcd(a: i32, b: i32) -> i32 {
match (a, b) {
(_, 0) => a,
(_, _) => gcd(b, a % b)
}
}
FizzBuzz
Haskell
fizzBuzz :: Int -> String
fizzBuzz n = case (n `mod` 3, n `mod` 5) of
(0, 0) -> "FizzBuzz"
(0, _) -> "Fizz"
(_, 0) -> "Buzz"
_ -> show n
main :: IO ()
main = do
mapM_ (putStrLn . fizzBuzz) [1..100]
Rust
fn fizz_buzz(n: i32) -> String {
match (n % 3, n % 5) {
(0, 0) => String::from("FizzBuzz"),
(0, _) => String::from("Fizz"),
(_, 0) => String::from("Buzz"),
_ => n.to_string()
}
}
fn main() {
(1..=100)
.map(fizz_buzz)
.for_each(|x| println!("{}", x));
}
この辺はmatch式使えば再現できますね！
パターンマッチが便利！
数列
四角数列
Haskell
squareNumbers :: [Integer]
squareNumbers = [n ^ 2 | n <- [1..]]
main = do
print $ take 10 squareNumbers
Rust
fn square_numbers() -> impl Iterator<Item = u64> {
(1..).map(|x| x * x)
}
fn main() {
let squares: Vec<u64> = square_numbers().take(10).collect();
println!("{:?}", squares)
}
無限リストからの生成！
式がシンプルで分かりやすい！
フィボナッチ数列
Haskell
fibonacci :: [Integer]
fibonacci = 1 : 1 : zipWith (+) fibonacci (tail fibonacci)
main = do
print $ take 10 fibonacci
Rust
fn fibonacci() -> impl Iterator<Item = u64> {
(0..).into_iter()
.scan((0, 1), |state, _| {
let next = state.0 + state.1;
state.0 = state.1;
state.1 = next;
Some(state.0)
})
}
fn main() {
let fibo: Vec<u64> = fibonacci().take(10).collect();
println!("{:?}", fibo);
}
無限リストからフィボナッチ数列の生成
Haskell美しすぎてやばい...
Rustで頑張ってみる...ワイにはこれが限界か...
ソート
クイックソート
Haskell
quickSort :: Ord a => [a] -> [a]
quickSort [] = []
quickSort (x:xs) =
quickSort [y | y <- xs, y <= x] ++ [x] ++ quickSort [y | y <- xs, y > x]
main = do
let list = [3, 2, 1, 9, 5, 6, 4, 8, 7, 10]
print $ quickSort list
Rust
fn quick_sort(arr: &Vec<i32>) -> Vec<i32> {
if arr.len() == 0 {
return arr.to_vec()
}
let pivot = arr[0];
let slice = &arr[1..];
let left = slice.iter().cloned()
.filter(|&x| x <= pivot).collect();
let right = slice.iter().cloned()
.filter(|&x| x > pivot).collect();
[quick_sort(&left), vec![pivot], quick_sort(&right)].concat()
}
fn main() {
let v = vec![3, 2, 1, 9, 5, 6, 4, 8, 7, 10];
println!("{:?}", quick_sort(&v));
}
ハアハア...
可能な限り近づけてはみた...
Haskellの(x:xs)とかチートですわ...リスト内包表記も便利すぎるし
探索
二分探索
Haskell
binarySearch :: Ord a => [a] -> a -> Maybe Int
binarySearch xs target = binarySearchHelper xs target 0 (length xs - 1)
binarySearchHelper :: Ord a => [a] -> a -> Int -> Int -> Maybe Int
binarySearchHelper xs target low high
| low > high = Nothing
| target == midVal = Just mid
| target < midVal = binarySearchHelper xs target low (mid - 1)
| target > midVal = binarySearchHelper xs target (mid + 1) high
where
mid = low + (high - low) `div` 2
midVal = xs !! mid
main = do
let list = [1, 3, 5, 7, 9, 11, 13, 15]
let target = 7
print $ binarySearch list target
Rust
use std::cmp::Ordering;
fn binary_search<T: Ord>(slices: &[T], target: &T) -> Option<i32> {
binary_search_helper(slices, target, 0, (slices.len() - 1) as i32)
}
fn binary_search_helper<T: Ord>(slices: &[T], target: &T, low: i32, high: i32) -> Option<i32> {
if low > high {
return None;
}
let mid = low + (high - low) / 2;
let mid_val = &slices[mid as usize];
match mid_val.cmp(target) {
Ordering::Equal => Some(mid),
Ordering::Greater => binary_search_helper(slices, target, low, mid - 1),
Ordering::Less => binary_search_helper(slices, target, mid + 1, high)
}
}
fn main() {
let list = vec![1, 3, 5, 7, 9, 11, 13, 15];
let target = 7;
match binary_search(&list, &target) {
Some(index) => println!("target found! index: {}", index),
None => println!("target not found")
}
}
遜色ない感じで実装できたかな？
まとめ
いかがだったでしょうか。
基本的なアルゴリズムからクイックソート、二分探索まで、いろいろトライできたのではと思います。
ではまた！