【学習メモ】無茶振りHaskell to Rustチャレンジ！

こんにちは！
昨日に引き続き、Rustの学習メモです。
今日は、Rustの文法を手に馴染ませるため、様々なアルゴリズムにチャレンジしたいと思います。

:::note
Rustを始めてまだ１週間程度ですので、不十分なコードあるかもしれませんが、ご容赦ください。
:::

# ルール
1. 対象のアルゴリズムを実装するコードを、ChatGPTにHaskellで書いてもらう
2. そのコードを、Rustで可能な限り再現する

純粋関数型言語であるHaskellのコードに、どこまで近づけるか！
チャレンジしていきたいと思います！

# 基本
まずは基本的なやつから！

### 階乗

```haskell:Haskell
fact :: Int -> Int
fact 0 = 1
fact n = n * fact (n - 1)
```
```rust:Rust
fn fact(n: i32) -> i32 {
    match n {
        0 => 1,
        _ => n * fact(n - 1)
    }
}
```



### 最大公約数（ユークリッドの互除法）

```haskell:Haskell
gcd' :: Int -> Int -> Int
gcd' a 0 = a
gcd' a b = gcd' b (a `mod` b)
```
```rust:Rust
fn gcd(a: i32, b: i32) -> i32 {
    match (a, b) {
        (_, 0) => a,
        (_, _) => gcd(b, a % b)
    }
}
```

### FizzBuzz

```haskell: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: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:Haskell
squareNumbers :: [Integer]
squareNumbers = [n ^ 2 | n <- [1..]]

main = do
  print $ take 10 squareNumbers
```
```rust: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:Haskell
fibonacci :: [Integer]
fibonacci = 1 : 1 : zipWith (+) fibonacci (tail fibonacci)

main = do
  print $ take 10 fibonacci
```
```rust: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: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: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: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: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")
    }
}
```
遜色ない感じで実装できたかな？

# まとめ
いかがだったでしょうか。
基本的なアルゴリズムからクイックソート、二分探索まで、いろいろトライできたのではと思います。
ではまた！