fold *を使ってHaskellでリストを作成する

Question

私はハスケルで次の問題を解決しようとしています。整数の場合、数字のリストを返します。制約はfold *関数（* = {r、l、1、l1}）の1つのみを使用しなければならないということです。

ような制約がなければ、コードは単純です：

list_digits :: Int -> [Int] 
list_digits 0 = [] 
list_digits n = list_digits r ++ [n-10*r] 
       where 
        r = div n 10 

しかし、どのように私は、基本的に空のリストから、数字のリストを成長させる倍*を使用していますか？

ありがとうございます。

Answer 1

これは宿題ですか？あなたがfoldrを使用することを要求する割り当てがかなり奇妙です。これはunfoldrでは自然な使用であり、foldrではないからです。 unfoldr :: (b -> Maybe (a, b)) -> b -> [a]ビルドリスト、一方foldr :: (a -> b -> b) -> b -> [a] -> bはリストを消費します。 foldrを使用してこの関数を実装すると、ひどく歪んでしまいます。命令型プログラミング言語で

listDigits :: Int -> [Int] 
listDigits = unfoldr digRem 
    where digRem x 
       | x <= 0 = Nothing 
       | otherwise = Just (x `mod` 10, x `div` 10) 

、これは基本的にwhileループです。ループの各反復はx `mod` 10を出力リストに追加し、x `div` 10を次の反復に渡します。 、で言う、Pythonのは、this'd

def list_digits(x): 
    output = [] 
    while x > 0: 
     output.append(x % 10) 
     x = x // 10 
    return output 

として書かしかしunfoldrは、私たちははるかに高いレベルでのループを表現することを可能にします。 unfoldrは、「一度に1つの項目を作成する」というパターンをキャプチャし、明示的にします。ループの逐次的な振る舞いを考える必要はなく、Pythonコードのようにリストが一度に1つの要素で構築されていることに気付く必要はありません。 unfoldrが何をしているのかを知るだけです。確かに、折りたたみや折り畳みを使ったプログラミングは慣れていますが、表現力を高めるためにはそれだけの価値があります。

あなたの割り当ては、マシンによってマークされ、それは本当にあなたには、以下の「id[]で卑劣なトリックを再生することができます（彼らはそれをしたし、なぜあなたはあなたの先生に依頼する必要があります）、あなたのプログラムのテキストに単語foldrを入力する必要がない場合-as- foldr "機能：

obfuscatedId = foldr (:) [] 
listDigits = obfuscatedId . unfoldr digRem 

Answer 2

unfoldrは割り当てが何を意味するのか、あなたはそれが別のものを涙ながらつのリストを構築、つまり、hylomorphismとしてfoldrを使用している場合、あなたはfoldrを使用して、これを書くことができ、おそらくですがダウン。

digits :: Int -> [Int] 
digits n = snd $ foldr go (n, []) places where 
    places = replicate num_digits() 
    num_digits | n > 0  = 1 + floor (logBase 10 $ fromIntegral n) 
      | otherwise = 0 
    go() (n, ds) = let (q,r) = n `quotRem` 10 in (q, r : ds) 

効果的に、私たちがここでやっていることは「マップを持つ状態」としてfoldrを使用しています。私たちは事前にその数字が何でないかをlog35を使って出力する必要があるので、数字の代わりに ユニット（()）の値を使用します。

先生がちょうどトップレベルでfoldrを持つためにこだわるなら、あなたはgoは、部分的に作ると離れて を得ることができますが：

digits' :: Int -> [Int] 
digits' n = foldr go [n] places where 
    places = replicate num_digits() 
    num_digits | n > 0  = floor (logBase 10 $ fromIntegral n) 
      | otherwise = 0 
    go() (n:ds) = let (q,r) = n `quotRem` 10 in (q:r:ds) 

これは、非正の数にわずかに異なる振る舞いを持っています

>>> digits 1234567890 
[1,2,3,4,5,6,7,8,9,0] 
>>> digits' 1234567890 
[1,2,3,4,5,6,7,8,9,0] 
>>> digits 0 
[] 
>>> digits' 0 
[0] 
>>> digits (negate 1234567890) 
[] 
>>> digits' (negate 1234567890) 
[-1234567890]