Haskellで「与えられた自然数を２以上の自然数の和に分解して表示する」プログラムを書きたい

Question

かなり久しぶりに質問投稿します。
よろしくお願いします。

Haskellで「与えられた自然数を２以上の自然数の和に分解して表示する」プログラムを書きたいのですが、うまくいきません。
以下は、Javaのソースコードで自分が実装したものです。
正常に動作しておりますね。

import java.util.Arrays;

public class App {
    public static void main(String[] args) throws Exception {
        int count = 0;
        int n = 6;
        int[] result = new int[10];

        count = calc(n, result, 0);
        System.out.println(count);
    }

    private static int calc(int n , int[] result, int i) {
        int count = 0;
        int[] result2 = Arrays.copyOf(result, 10);

        if(n == 2){  // output
            result[i] += 2;
            System.out.println(Arrays.toString(result));
            count = 1;
        } else {
            if(n > 3){
                result[i] += 2;
                count += calc(n-2, result, i+1);
            }
            if(n > 2){
                result2[i] +=1;
                count += calc(n-1, result2, i);
            }
        }
        return count;
    }
}

実行結果

[2, 2, 2, 0, 0, 0, 0, 0, 0, 0]
[2, 4, 0, 0, 0, 0, 0, 0, 0, 0]
[3, 3, 0, 0, 0, 0, 0, 0, 0, 0]
[4, 2, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 0, 0, 0, 0, 0, 0, 0, 0, 0]
5

まぁ・・・実行結果の表示は悪いのですが・・・(0 と count は別に要らないので。)

上記のプログラムをHaskellでも書きたいです。

decompose :: Int -> [[Int]]
decompose n = decomposeHelper n 2

decomposeHelper :: Int -> Int -> [[Int]]
decomposeHelper 0 _ = [[]]
decomposeHelper n start
    | n < 0     = []
    | otherwise = [ x : rest | x <- [start..n], rest <- decomposeHelper (n - x) x]

main :: IO ()
main = do
    putStrLn "Enter an integer:"
    input <- getLine
    let number = read input :: Int
    let decompositions = decompose number
    putStrLn $ "Possible decompositions of " ++ show number ++ ":"
    mapM_ print decompositions
    

実行結果 「うーーーん。」

Enter an integer:
6
Possible decompositions of 6:
[2,2,2]
[2,4]
[3,3]
[6]

これだと [4, 2]が抜けてしまいますね。
異なる順序を別の和として表現したいので・・・

State Monad や Writer Monadも試してみたのですが、
Monad の do内で 以下のようにif式を連続で記述できないんですよね。
必ず if - else のセットで記述しないといけないので。

if n > 3 then do 
...
if n > 2 then do 
...

何か良い解決策ないでしょうか？

ポイントはフィボナッチ数列の構造を利用している点です。
もし可能であれば、Monadを使用した場合と使用しない場合の両方を教えてくださると助かります。

Comments

[winterboum]

はて、、、
加える順に違いがあれば別の解ということでしょうか。
４＋２ と ２＋４は別物？

[strike1217]

その通りです。
順序を考慮しています。

[winterboum]

了解

Answer 1

Haskellで書く場合、こちらのようになると思います。

decompose :: Int -> [[Int]]
decompose 0 = [[]]
decompose n = [ x : rest | x <- [2..n], rest <- decompose (n - x)]

Writerモナドを使ってJavaのソースを再現すると、以下のようになると思います。
ただし、iの意味を変えていて、元のソースで言うとresult[i]を受け渡す形にしています。
あと、出力されるリストの中身が前後反転しています。
(最初ifで書いていましたが、whenの存在を思い出したので書き換えました)

import Control.Monad.Writer

decompose :: Int -> [[Int]]
decompose n = execWriter $ calc n [] 0

calc :: Int -> [Int] -> Int -> Writer [[Int]] ()
calc 2 result i = tell [i + 2 : result]
calc n result i = do
    when (n > 3) $ calc (n - 2) (i + 2 : result) 0
    when (n > 2) $ calc (n - 1) result (i + 1)

奇抜なアイディアをご所望とのことですが、あとは差分リストを使うぐらいしか思いつきません。
コードの見た目はWriterモナドとあまり変わりません。

decompose :: Int -> [[Int]]
decompose n = calc n [] 0 []

calc :: Int -> [Int] -> Int -> [[Int]] -> [[Int]]
calc 2 result i = ((i + 2 : result):)
calc n result i = (if n > 3 then calc (n - 2) (i + 2 : result) 0 else id) .
                  (if n > 2 then calc (n - 1) result (i + 1) else id)

Comments

[strike1217]

ほぇ・・・
普通に凄いです！
素晴らしい！！

[strike1217]

別解もあったら教えてください。
奇抜なアイディアとか大好きです。