Longest common prefix: Difference between revisions

Content added Content deleted
m (format)
m (→‎JS ES6: Updated primitives and output.)
Line 1,856: Line 1,856:
===ES6===
===ES6===
<lang javascript>(() => {
<lang javascript>(() => {
'use strict';
"use strict";

// -------------- LONGEST COMMON PREFIX --------------


// lcp :: (Eq a) => [[a]] -> [a]
// lcp :: (Eq a) => [[a]] -> [a]
const lcp = xs => {
const lcp = xs => {
const go = xs =>
const go = ws =>
xs.some(isNull) ? (
ws.some(isNull) ? (
[]
[]
) : cons(
) : [ws.map(head)].concat(
map(head, xs),
go(ws.map(tail))
⚫
go(map(tail, xs))
);
);

return concat(map(
head,
return takeWhile(allSame)(
takeWhile(
go(xs.map(s => [...s]))
⚫
allSame,
go(map(chars, xs))
)
)
));
.map(head)
⚫
.join("");

};
};




// TEST ---------------------------------------------
// ---------------------- TEST -----------------------

⚫
// main :: IO ()
⚫
const main = () => [
⚫
["interspecies", "interstellar", "interstate"],
⚫
["throne", "throne"],
⚫
["throne", "dungeon"],
⚫
["cheese"],
⚫
[""],
⚫
["prefix", "suffix"],
⚫
["foo", "foobar"]
].map(showPrefix).join("\n");



// showPrefix :: [String] -> String
// showPrefix :: [String] -> String
const showPrefix = xs =>
const showPrefix = xs =>
concat([show(xs), ' --> ', show(lcp(xs))]);
`${show(xs)} -> ${show(lcp(xs))}`;


⚫
// main :: IO ()
⚫
const main = () => {
const strResults = unlines(map(
⚫
showPrefix, [
⚫
["interspecies", "interstellar", "interstate"],
⚫
["throne", "throne"],
⚫
["throne", "dungeon"],
⚫
["cheese"],
[""],
⚫
["prefix", "suffix"],
⚫
["foo", "foobar"]
⚫
]
⚫
));
⚫
return (
// console.log(strResults),
⚫
strResults
);
};


// GENERIC FUNCTIONS --------------------------------
// ---------------- GENERIC FUNCTIONS ----------------


// allSame :: [a] -> Bool
// allSame :: [a] -> Bool
Line 1,908: Line 1,903:
0 === xs.length || (() => {
0 === xs.length || (() => {
const x = xs[0];
const x = xs[0];

return xs.every(y => x === y)
return xs.every(y => x === y);
})();
})();


// chars :: String -> [Char]
const chars = s => s.split('');


// concat :: [[a]] -> [a]
// head :: [a] -> a
// concat :: [String] -> String
const head = xs =>
const concat = xs =>
xs.length ? (
0 < xs.length ? (() => {
xs[0]
⚫
) : undefined;
const unit = 'string' !== typeof xs[0] ? (
[]
) : '';
return unit.concat.apply(unit, xs);
})() : [];


// cons :: a -> [a] -> [a]
const cons = (x, xs) => [x].concat(xs);

// head :: [a] -> a
const head = xs => xs.length ? xs[0] : undefined;


// isNull :: [a] -> Bool
// isNull :: [a] -> Bool
// isNull :: String -> Bool
// isNull :: String -> Bool
const isNull = xs =>
const isNull = xs =>
Array.isArray(xs) || ('string' === typeof xs) ? (
// True if xs is empty.
1 > xs.length
1 > xs.length;
) : undefined;


// map :: (a -> b) -> [a] -> [b]
const map = (f, xs) =>
⚫
(Array.isArray(xs) ? (
xs
) : xs.split('')).map(f);


// show :: a -> String
// show :: a -> String
const show = JSON.stringify;
const show = JSON.stringify;



// tail :: [a] -> [a]
// tail :: [a] -> [a]
const tail = xs => 0 < xs.length ? xs.slice(1) : [];
const tail = xs =>
⚫
0 < xs.length ? (
⚫
xs.slice(1)
⚫
) : [];



// takeWhile :: (a -> Bool) -> [a] -> [a]
// takeWhile :: (a -> Bool) -> [a] -> [a]
// takeWhile :: (Char -> Bool) -> String -> String
const takeWhile = p =>
const takeWhile = (p, xs) => {
xs => {
const lng = xs.length;
const i = xs.findIndex(x => !p(x));
return 0 < lng ? xs.slice(
0,
until(
i => lng === i || !p(xs[i]),
i => 1 + i,
0
)
) : [];
};


// unlines :: [String] -> String
return -1 !== i ? (
const unlines = xs => xs.join('\n');
xs.slice(0, i)
⚫
) : xs;
⚫
};


// until :: (a -> Bool) -> (a -> a) -> a -> a
const until = (p, f, x) => {
let v = x;
while (!p(v)) v = f(v);
return v;
};


// MAIN ---
// MAIN ---
Line 1,977: Line 1,948:
})();</lang>
})();</lang>
{{Out}}
{{Out}}
<pre>["interspecies","interstellar","interstate"] --> "inters"
<pre>["interspecies","interstellar","interstate"] -> "inters"
["throne","throne"] --> "throne"
["throne","throne"] -> "throne"
["throne","dungeon"] --> []
["throne","dungeon"] -> ""
["cheese"] --> "cheese"
["cheese"] -> "cheese"
[""] --> []
[""] -> ""
["prefix","suffix"] --> []
["prefix","suffix"] -> ""
["foo","foobar"] --> "foo"</pre>
["foo","foobar"] -> "foo"</pre>


=={{header|jq}}==
=={{header|jq}}==
Retrieved from "https://rosettacode.org/wiki/Longest_common_prefix"