2017-02-06 4 views
1

Я новичок в Haskell. мне трудно понять, что ниже подмножество программы с рекурсией. Как он оценивает?Haskell Recursion Subsets

subset :: [a] -> [[a]] 
subset [] = [[]] 
subset (x:xs) = [zs | ys <- subset xs, zs <- [ys,(x:ys)]] 

выход: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Когда я вручную оценить его подведении ниже

Ручной режим: [],[3],[2],[1,2]

мне не хватает какой-то логики здесь вы можете, пожалуйста, помогите мне понять приведенную выше концепцию рекурсии и какую часть инструкции охраны будет оценена сначала, порядок оценки?

+0

Только совет: отформатируйте большие куски кода, выделите его и нажмите ctrl + k. Только. Используйте «' s »для небольших кусочков. – Carcigenicate

+1

Попробуйте выразить, как последняя строка строит свой результат на английском языке. Я думаю, что это даст понять, как это работает. – Thilo

+0

Я не могу удержаться от указания этого однострочного камня, который делает то, что вы хотите. Он использует 'filterM' из' Control.Monad'. 'subset = filterM (const [False, True])'. И при этом вы получаете тот же результат (хотя и по-разному) как «подмножество» - он не менее эффективен! – Alec

ответ

2

В последней строке указано, что набор подмножеств x:xs представляет собой набор подмножеств xs вместе с x, добавленным к каждому из этих наборов.

Другой способ положить его в том, что

zs <- [ys,(x:ys)] 

генерирует ровно два множества, ys и x:ys для каждого ys, который является одним из подмножеств xs.