Изучаю Haskell

[Cfon]

Очередная шифрограмма от Хаскелл

words _ [] = []
words p s = w : words p s'
    where
        (w, s') = f p $ dropWhile p s
        f p (x:xs) | (not . p) x = (x:ys, zs) where (ys, zs) = f p xs
        f _ xs = ([], xs)

Что она делает? Получает предикат сравнения, строку, и возвращает список слов.. все так коротко? я кайфую

words (==' ') "Lorem Ipsum is simply dummy text of the printing and typesetting industry."
// ["Lorem","Ipsum","is","simply","dummy","text","of","the","printing","and","typesetting","industry."]

Задача та же перевести на JS

Кстати в Хаскелле отступы имееют значение! Тут аля как их не расставишь, но у меня с этим не было проблем ибо я всегда нормально их ставил
но вот те кто не любит отступы будут в га*не
Вроде в Пайтоне также. Наверно кодеры Хаскелла и Пайтон дружат

Сообщение отредактировано: Cfon - 27.10.18, 12:31

[Serafim]

'Lorem Ipsum is simply dummy text of the printing and typesetting industry.'.split(' ')

[Cfon]

Цитата Serafim @ 28.10.18, 00:27

'Lorem Ipsum is simply dummy text of the printing and typesetting industry.'.split(' ')

нет надо показать реализацию JS кода что привел на Haskell
То что в JS есть свои функции для обработки строк, я естесно в курсе как бы не наслышке, мой здесь интерес реализовать их в функциональном стиле.
Кстати в Хаскелле уже есть готовая функция words, я ее тут немного переклепал для практики

Догадываюсь что тут мало Хаскелистов (, а может и нет вапще ) и приведеный мной код не понятен многим, поэтому я ща его расшифрую

Короче даю построчный разбор кода

words _ [] = [] // 1
words p s = w : words p s' // 2
     where
         (w, s') = f p $ dropWhile p s // 3
         f p (x:xs) | (not . p) x = (x:ys, zs) where (ys, zs) = f p xs // 4
         f _ xs = ([], xs) // 5

Немного поясню стиль написания функций на Хаскелл основан на совпадении образцов (patterns matching), т.е. пишутся простые выражения (уравнения), которые потом выборочно вычисляются в зависимости от совпадения.
1 - совпадение срабатывает в случае когда words вызывается на пустом списке, он же является завершающим вызовом рекурсного вызова words
2 - идет рекурсивный вызов words
3 - вспомогательная функция f собственно выполняет всю работу по разделению слов, вызов dropWhile p s откидывает пробелы вначале строки s и предает ее в функцию f
4 - идет рекурсивный вызов f в результате каждого шага рекурсии возвращется пара или говоря в терминах Хаскелля кортеж (ys, zs), далее он намного изменяется, точнее сам то кортеж не меняется, т.к. в Хаскелл нет переменных в классическом понимании, это просто некое имя для значения или выражения, создается новый кортеж (x:ys, zs) с измененым списком ys, если говорить точнее к нему в голову добавляется значение переменной x
5 - завершающий вызов рекурсии
еще проще сложно описать т.к. надо весь язык капать

Сообщение отредактировано: Cfon - 28.10.18, 07:44

[Cfon]

Приветствую вот накодил получилась жесть, как по мне что то не то

function words(p, s) {
    if (s === '') return [];
 
    function f(p, s) {
        const a = [...s];
        const {c, s1} = { c: a.shift(), s1: a.join('')};
  
        if (!p(c)) {
            const {w, s2} = f(p, s1);
            return {w: [c,...w].join(''), s2};
        }
        return {w:[], s2:s1};
    };
    
    const {w, s2} = f(p, dropWhile(p, [...s]).join(''));
    return [w, ...words(p, s2)];
}
 
const s = "Lorem Ipsum is simply dummy text of the printing and typesetting industry. ";
const ws = words(c => c === ' ', s);
console.log(ws);
// ["Lorem","Ipsum","is","simply","dummy","text","of","the","printing","and","typesetting","industry."]

в коде есть где то баг, если исходная строка не заканчивается пробелом, то все летит лесом
ПС. dropWhile взят из прошлых моих творений что в предыдущих постах постах
ладно чет устал я если у вас есть желание найти баг, ну или свой пример запостить велком, а я отдыхать!

Сообщение отредактировано: Cfon - 28.10.18, 12:41

[Cfon]

Баг нашел, дело в строчке где происходит отделение символа от строки, но пока решения не нашел, временно поставил императивный костыль

function words(p, s) {
    if (s === '') return [];
 
    function f(p, s) {
        let [c, ...s1] = s; //<--- тут баг
        if (c === undefined) c = ' '; //<-- костыль
 
        if (!p(c)) {
            const {w, s2} = f(p, s1);
            return {w: [c, ...w], s2};
        }
        return {w:[], s2: s1};
    };
    
    const {w, s2} = f(p, dropWhile(p, [...s]));
    return [w.join(''), ...words(p, s2.join(''))];
}

Попутно подрихтовал код заюзав деструктиризацию массива вместо прямых манипуляций

const a = [...s];
const {c, s1} = { c: a.shift(), s1: a.join('')};

на

let [c, ...s1] = s;

Сообщение отредактировано: Cfon - 28.10.18, 17:35

[Serafim]

Цитата Cfon @ 28.10.18, 06:57

нет надо показать реализацию JS кода что привел на Haskell

function *words(sentence, separator) {
    let buffer = '';
 
    for (let char of sentence) {
        if (char === separator) {
            yield buffer;
            buffer = '';
            continue;
        }
 
        buffer += char;
    }
}

Прикреплённый файл123123.jpg (277,2 Кбайт, скачиваний: 363)

Сообщение отредактировано: Serafim - 28.10.18, 22:46

[Cfon]

Цитата Cfon @ 28.10.18, 17:26

Баг нашел, дело в строчке где происходит отделение символа от строки, но пока решения не нашел, временно поставил императивный костыль

Пофиксил

function words(p, s) {
    if (s === '') return [];
 
    function f(p, s) {
        const [c = ' ', ...s1] = s;
            //    ^^ значение по умолчанию
 
        if (!p(c)) {
            const {w, s2} = f(p, s1);
            return {w: [c, ...w], s2};
        }
        return {w:[], s2: s1};
    };
    
    const {w, s2} = f(p, dropWhile(p, [...s]));
    return [w.join(''), ...words(p, s2.join(''))];
}

Вроде более менее приближен к Хаскелл-стилю, надо еще подрихтовать формы

Добавлено 29.10.18, 05:56

Цитата Serafim @ 28.10.18, 22:43

function *words(sentence, separator) {
    let buffer = '';
 
    for (let char of sentence) {
        if (char === separator) {
            yield buffer;
            buffer = '';
            continue;
        }
 
        buffer += char;
    }
}

ну и где тут функциональный подход Хаскелл?

очередная императивная реализация

Сообщение отредактировано: Cfon - 29.10.18, 05:58

[Cfon]

Вот еще немного рихтовки

function words(p, s) {
  if (s === '') return []; // 1
 
  const f = (p, s) => {
    const [x = ' ', ...xs] = s;
    return !p(x)
      ? ({ys, zs} = f(p, xs), {ys: [x,...ys], zs}) // 4
      : {ys:[], zs: xs} // 5
  };
 
  const {ys: w, zs: s1} = f(p, dropWhile(p, [...s])); // 3
  return [w.join(''), ...words(p, s1.join(''))]; // 2
}

Оригинал на Хаскелле

words :: (Char -> Bool) -> String -> [String]
words _ [] = [] // 1
words p s = w : words p s' // 2
    where
        (w, s') = f p $ dropWhile p s // 3
         f p (x:xs) | (not . p) x = (x:ys, zs) where (ys, zs) = f p xs // 4
         f _ xs = ([], xs) // 5

Почти один в один

В ходе исследования кода JS в попытке приблизить его в функциональному стилю Haskell должен отметить операторы запятая и тернарный, а также синтаксис деструктуризации объектов и массивов, и остаточных элементов ES6 Без них мало что получилось!
А также группе Helloween и ушам Audio Technica! Они хорошо изолировали меня от окружающих!

Сообщение отредактировано: Cfon - 29.10.18, 12:55

[Cfon]

Пардон! Грубая ошибка! Так нельзя

function words(p, s) {
  if (s === '') return [];
 
  const f = (p, s) => {
    const [x = ' ', ...xs] = s;
    return !p(x)
      ? ({ys, zs} = f(p, xs), {ys: [x,...ys], zs})
       //  ^^^^^ создаются глобальные переменные!!
      : {ys:[], zs: xs}
  };
 
  const {ys: w, zs: s1} = f(p, dropWhile(p, [...s]));
  return [w.join(''), ...words(p, s1.join(''))];
}

Обратно к корректной форме

function words(p, s) {
    if (s === '') return [];
 
    const f = (p, s) => {
        const [x = ' ', ...xs] = s;
        if (!p(x)) {
            const {ys, zs} = f(p, xs);
               //   ^^^^  OK, локальные переменные
            return {ys: [x,...ys], zs};
        }
        return {ys:[], zs: xs};
    };
 
    const {ys: w, zs: s1} = f(p, dropWhile(p, [...s]));
    return [w.join(''), ...words(p, s1.join(''))];
}

Фан версия!

function words(p, s) {
    if (s === '') return [];
 
    const f = (p, s) => (() => {
        const [x = ' ', ...xs] = s;
        return !p(x)
            ? (() => {const {ys, zs} = f(p, xs);return {ys: [x,...ys], zs}})()
            : {ys:[], zs: xs}
    })();
 
    const {ys: w, zs: s1} = f(p, dropWhile(p, [...s]));
    return [w.join(''), ...words(p, s1.join(''))];
}

Сообщение отредактировано: Cfon - 29.10.18, 18:15

[Serafim]

Цитата Cfon @ 29.10.18, 05:47

ну и где тут функциональный подход Хаскелл?

Он медленный, жрёт кучу оперативы и не читаемый.

[Cfon]

Цитата Serafim @ 29.10.18, 19:38

Он медленный, жрёт кучу оперативы и не читаемый.

Вроде как Haskell рекурсии оптимизирует и они не жрут память, читал где то
а не читаемый потому что функциональный стиль требует иного подхода к чтению

ОК очередное задание, переписать на JS код, который парсит строку на слова и возвращает список из числа повторений каждого слова и самого слова
Вот образец

*Main> wordNums "hello world hello"
[(2,"hello"),(1,"world")]

Код на Хаскелле

wordNums :: String -> [(Int, String)]
wordNums s = [(length ws, head ws) | ws <- group . qsort . words (==' ') $ s]
 
words :: (Char -> Bool) -> String -> [String]
words p s = case dropWhile p s of
  "" -> []
  s' -> w : words p s''
    where (w, s'') = split p s'
 
qsort :: (Ord a) => [a] -> [a]
qsort [] = []
qsort (x : xs) =
    qsort [y | y <- xs, y <= x] ++
    [x] ++
    qsort [y | y <- xs, y > x]
 
group :: (Eq a) => [a] -> [[a]]
group [] = []
group (x:xs) = (x:ys): group zs where (ys, zs) = split (/= x) xs
 
split :: (a -> Bool) -> [a] -> ([a], [a])
split p (x:xs) | (not . p) x = (x:ys, zs) where (ys, zs) = split p xs
split _ xs = ([], xs)

Функции words, qsort уже переписаны на JS в предыдущих постах, я их для наглядности сюда тоже перенес. Осталось group и wordNums. Ну а split я просто вынес из words для повторного применения в group. Она делить список (строку) на две части согласно предику

Пояснения к коду Хаскелл.
words - получает исходную строку и возвращает список слов
group - получает список слов и выделяет рядом лежащие совпадающие слова в отдельные списки, ну возвращает его (список списков)
sort - понятно сортирует
split - уже писал выше
ВСЕ! да и я тоже буду переводить го кто шустрее

Сообщение отредактировано: Cfon - 30.10.18, 11:22

[Cfon]

Готова!

function words(p, s) {
    if (s === '') return [];
    const [w, s1] = split(p, dropWhile(p, [...s]));
    return [w.join(''), ...words(p, s1.join(''))];
}
 
function group(xs) {
    if (xs.length == 0) return [];
    const [x, ...xs1] = xs;
    const [ys, zs] = split(x1 => x1 !== x, xs1);
    return [[x, ...ys], ...group(zs)];
}
 
function split(p, xs) {
    if (xs.length == 0) return [[],[]];
    const [x, ...xs1] = xs;
    if (!p(x)) {
        const [ys, zs] = split(p, xs1);
        return [[x, ...ys], zs];
    }
    return [[], xs];
}
 
function dropWhile(p, xs) {...} // см выше
function qsort(xs) {...} // см quicksort
 
const wordNums = s =>
    group( qsort( words(c => c == ' ', s))).map(ws => ([ws.length, ws[0]]));
 
const s = 'hello world hello';
console.log(wordNums(s));
// [ [ 2, 'hello' ], [ 1, 'world' ] ]

Получилось почти в функциональном стиле, почему почти?
1 - в функциях больше одного return
2 - наличие присваиваний
Все это вносит некий императизм
Но несмотря на это в обшем код смотрится функционально!
Особенно функция wordNums изящно не правда ли?

Сообщение отредактировано: Cfon - 01.11.18, 05:21

[Serafim]

Цитата Cfon @ 30.10.18, 10:52

Вроде как Haskell рекурсии оптимизирует и они не жрут память, читал где то

А зачем оптимизировать что-то, если можно просто вернуть корутину?

Добавлено 30.10.18, 19:22

Цитата Cfon @ 30.10.18, 19:01

Но несмотря на это в обшем код смотрится функционально!

Код смотрится отвратно. Я могу сократить его в 10 раз и сделать на порядки читаемее... Хотя, постой, кажется, я уже это делал

[Cfon]

Цитата Serafim @ 30.10.18, 19:20

Код смотрится отвратно. Я могу сократить его в 10 раз и сделать на порядки читаемее... Хотя, постой, кажется, я уже это делал

Го жду

[Serafim]

Изучаю Haskell (сообщение #3781730)