Простые функции для SML/NJ

Question

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

1. Наборы могут быть представлены в виде списков. Элементы набора могут отображаться в любом порядке в списке, но не должно быть больше одного . Вхождение элемента в список.

(a) Определите dif (A, B), чтобы вычислить разницу в наборах A и B, A-B.

(b) Определить декартову (A, B) для вычисления декартова произведения множества A и множества B, {(a, b) | a∈A, b∈B}.

c) Рассмотрим математическую индукционную проверку для следующего содержания: Если множество A имеет n элементов, то набор параметров A имеет 2n элементов. Следуя доказательству, определите poweret (A) для вычисления набора набора A, {B | B ⊆ A}.

(d) Определите функцию, которая задает набор A и натуральное число k, возвращает набор всех подмножеств A размера k.

(* Takes in an element and a list and compares to see if element is in list*) 

fun helperMem(x,[]) = false 
| helperMem(x,n::y) = 
     if x=n then true 
     else helperMem(x,y); 

(* Takes in two lists and gives back a single list containing unique elements of each*) 

fun helperUnion([],y) = y 
| helperUnion(a::x,y) = 
     if helperMem(a,y) then helperUnion(x,y) 
     else a::helperUnion(x,y); 

(* Takes in an element and a list. Attaches new element to list or list of lists*) 
fun helperAttach(a,[]) = [] 
    helperAttach(a,b::y) = helperUnion([a],b)::helperAttach(a,y); 


    (* Problem 1-a *) 
fun myDifference([],y) = [] 
| myDifference(a::x,y) = 
    if helper(a,y) then myDifference(x,y) 
    else a::myDifference(x,y); 

(* Problem 1-b *) 
fun myCartesian(xs, ys) = 
    let fun first(x,[]) = [] 
    |  first(x, y::ys) = (x,y)::first(x,ys) 
     fun second([], ys) = [] 
    |  second(x::xs, ys) = first(x, ys) @ second(xs,ys) 
    in  second(xs,ys) 
    end; 


(* Problem 1-c *) 
fun power([]) = [[]] 
| power(a::y) = union(power(y),insert(a,power(y))); 

Я никогда не получил проблемы 1-й, так как они мне потребовалось некоторое время, чтобы получить. Любые предложения по сокращению этих сокращений? Была еще одна проблема, которую я не получил, но я хотел бы знать, как ее решить для будущих тестов.

1. (проблема лестницы) Вы хотите пойти вверх по лестнице п (> 0) шагов. В свое время вы можете пройти один шаг, два шага или три шага. Но, например, , если есть один шаг влево, вы можете пойти только на один шаг , а не на два или три шага. Сколько разных способов для подниматься по лестнице? Решите эту проблему с помощью sml. (a) Рекурсивно решает его . (b) Решите его итеративно.

Любая помощь по решению этой проблемы?

Answer 1

Ваши функции набора выглядят хорошо. Я не стал бы менять что-либо принципиальное о них, кроме, возможно, их форматирования и именования:

fun member (x, []) = false 
    | member (x, y::ys) = x = y orelse member (x, ys) 

fun dif ([], B) = [] 
    | dif (a::A, B) = if member (a, B) then dif (A, B) else a::dif(A, B) 

fun union ([], B) = B 
    | union (a::A, B) = if member (a, B) then union (A, B) else a::union(A, B) 

(* Your cartesian looks nice as it is. Here is how you could do it using map: *) 
local val concat = List.concat 
     val map = List.map 
in fun cartesian (A, B) = concat (map (fn a => map (fn b => (a,b)) B) A) end 

Ваша сила тоже очень аккуратная. Если вы вызываете свою функцию insert, она заслуживает комментария о вводе чего-то во многие списки. Возможно, insertEach или подобное имя лучше.

В вашей последней задаче, поскольку это проблема подсчета, вам не нужно генерировать фактические комбинации шагов (например, в виде списков шагов), а только считать их. Используя рекурсивный подход, попробуйте записать базовые случаи, как они описаны в описании проблемы.

I.e., сделайте функцию steps : int -> int, где предварительно рассчитано количество способов выполнить 0, 1 и 2 шага, но для n шагов, n> 2, вы знаете, что существует набор комбинаций шагов, которые начинаются с либо 1, 2 или 3 шага плюс числовые комбинации взятия n-1, n-2 и n-3 шагов соответственно.

Используя итеративный подход, начинайте снизу и используйте параметризованные переменные подсчета. (Извините за смутный намек здесь.)